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

Proceso de ejecución de las llamadas al sistema

Código en C++

#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

Árbol de llamadas al sistema creado por la función recursiva Fibonacci

Código en C++

#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

Código en C++

#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;
}