Recursividad

Uno de los conceptos más poderosos de la programación, es la capacidad de un método o función, de llamarse a si misma de forma recurrente, a fin de dividir un problema complejo en problemas cada vez más pequeños.

Uno de los ejemplos clásicos de definiciones recurrentes, que pueden ser resueltas por recursividad, es el de los números factoriales

En computación, necesitamos determinar dos cosas, antes de desarrollar un programa que use recursividad;

• La condición de salida
• La operación de recursividad

En el caso de los factoriales, es simple,
- Condición de salida, si n=0 entonces, su factorial es 1 (ojo, si n=1 su factorial es 1 también)
- Operación recursiva, resultado de f(n) = n multiplicado por f(n-1)

En Java quedaría así.


La condición de salida, garantiza que si el número ingresado es 0 o 1, debe retornar como resultado 1.
Mientras que si el número es mayor, llama una y otra vez a la función con un número menos 1 hasta que su valor es igual a 1 y se "devuelve" con los resultados.

OJO! Si la condición de salida no es satisfecha, el programa se sigue llamando hasta que ya no queda memoria disponible en el equipo y lo deja "colgado" [Esto se llama loop infinito]

Veamos la traza del programa para 3!



Ahora, otros problemas clásicos que se resuelven facilmente con el método recursivo son;
- Serie de Fibonacci
- Torres de Hanoi
otros ejemplos algo más complejos
- Determinar los ceros de una ecuación polinómica
- El cubo Rubick
- La función de Ackermann
- Método de ordenamiento Quicksort y Bubble

Ahora, la funcion para calcular la serie de Fibonacci es muy parecida;
F(n)=F(n-1)+F(n-2)
donde
F(0)=0
Adicionalmente, F(1) es igual a 1.

Así, el programa queda parecido a esto
- Condición de salida,Si número menor a 2 ==> fibonacci es el número
- Operación recursiva, resultado de f(n) es igual a la suma f(n-1) + f(n-2)

El código, lo deberían poder hacer por su cuenta .-)
Suerte