Estructuras de Datos I - Recursividad

Vista previa del material en texto

Estructuras de Datos I
Recursividad
Recursividad
Capacidad de una función / método de activarse a si mismo
Elementos básicos de una función recursiva:
Al menos una parte recursiva:
Realiza la activación de la misma función
Se dice que “se llama a si misma”, en realidad se activa a si misma, ya que el llamado solo es en el main.
Al menos una parte no recursiva:
Mejor conocido como el criterio de paro, proporciona una manera de parar la recursividad.
Se dice que “es para evitar ciclarlo”
Recursividad – Ejemplos
Sumatoria de un rango de números
Sum(5) = 5 + 4 + 3 + 2 + 1
Sum(4) = 4 + 3 + 2 + 1
Sum(3) = 3 + 2 + 1
Sum(2) = 2 + 1
Sum(1) = 1
Sum(5) = 5 + Sum(4)
Sum(4) = 4 + Sum(3)
Sum(3) = 3 + Sum(2)
Sum(2) = 2 + Sum(1)
Sum(1) = 1
Sum(n) = n + Sum(n-1)
Recursividad – Ejemplos
Sumatoria de un rango de números
Int sum(int n);
Int main(){
	int aux;
	cout << “Dame un numero: ”
	cin >> aux;
	sum(aux);
}
Int sum(int n){
If(n == 1 || n == 0) return 1
Return n + sum(n-1);
}
main()
cout
cin
Sum(5)
Sum(4)
Sum(3)
Sum(2)
Sum(1)
Recursividad – Ejemplos
Fibonacci = 1 1 2 3 5 8 13 21 34 …
Posición = 0 1 2 3 4 5 6 7 8 …
Fibonacci(5) = 5 + 3 = 8
Fibonacci(4) = 3 + 2 = 5
Fibonacci(3) = 2 + 1 = 3
Fibonacci(2) = 1 + 1 = 2
Fibonacci(1) = 1 = 1
Fibonacci(0) = 1 = 1
Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
Fibonacci(2) = Fibonacci(1) + Fibonacci(0)
Fibonacci(1) = 1
Fibonacci(0) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Recursividad – Ejemplos
Fibonacci(3)
Fibonacci(2)
Fibonacci(1)
Fibonacci(0)
1
1
Fibonacci(1)
1
2
3