> For the complete documentation index, see [llms.txt](https://ooi.gitbook.io/courses/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ooi.gitbook.io/courses/ooi-2019/cursos-online/clase-recursion-introductorio.md).

# Clase recursión introductorio

### Video de la sesión:

<https://youtu.be/o0sxJjzCgXQ>

### Función factorial

![Definición matemática de la función factorial](/files/-L_k2JPUdpvsOYn9-knA)

![Proceso de ejecución de las llamadas al sistema](/files/-L_k2RKHwWu0p-h8BDF8)

#### Código en C++

```cpp
#include <bits/stdc++.h>

using namespace std;

int f(int n) {
	if(n == 0) {
		return 1;
	}
	else {
		return n * f(n - 1);
	}
}


int main() {

	int n, res;
	cin >> n;

	res = f(n);

	cout << res;

	return 0;
}
```

### Función Fibonacci

![Definición matemática de la función Fibonacci](/files/-L_k2kcy5G1YMne1_Tk3)

![Árbol de llamadas al sistema creado por la función recursiva Fibonacci](/files/-L_k2qStR0E_RI5VeyU9)

#### Código en C++

```cpp
#include <bits/stdc++.h>

using namespace std;

int fib(int n) {
	if(n == 0 || n == 1) {
		return 1;
	}
	else {
		return fib(n - 1) + fib(n - 2);
	}
}


int main() {

	int n, res;
	cin >> n;

	res = fib(n);

	cout << res;

	return 0;
}
```

### Exponenciación rápida usando recursión

El siguiente algoritmo es la implementación de exponenciación utilizando la técnica "Divide y vencerás". Representa la función de elevar un número `a` a la potencia `n`.

![Definición de la función de exponenciación rápida de forma recursiva](/files/-L_k3NjIA_wYbgGGN6kc)

#### Código en C++

```cpp
#include <bits/stdc++.h>

using namespace std;

int fast_pow(int a, int n) {// Modela la operacion a elevado a la potencia n
	if(n == 1) {
		return a;
	}
	else if(n % 2 == 0) {
		int res;
		res = fast_pow(a, n/2);
		return res * res;
	}
	else {
		return a * fast_pow(a, n - 1);
	}
}


int main() {
	int x, n;
	cin >> x >> n;

	cout << fast_pow(x, n);


	return 0;
}
```