Java básico #9

1.9 Recursividad

           Es una técnica potente de programación que puede utilizarse en lugar de la iteración. Por ejemplo, para escribir un método que calcule el factorial entero no negativo, podemos hacerlo a partir de la definición de factorial:

Si n=0 entonces

0!=1

Si n>0 entonces

n!=n*(n-1)*(n-2)...*3*2*1

Esto dará lugar a una solución iterativa mediante un bucle for:

1. // Método Java no recursivo para calcular el factorial de un número
2. public double factorial(int n){
3.     double fact=1;
4.     int i;
5.     if (n==0)
6.         fact=1;
7.     else
8.         for(i=1;i<=n;i++)
9.             fact=fact*i;
10.  return fact;
11. }

          Pero existe otra definición de factorial en función de sí misma:

0! = 1

n! = n · (n – 1)! ,    si n > 0   (El factorial de n es n por el factorial de n-1)

          Esta definición da lugar a una solución recursiva del factorial en Java:

1. // Método Java recursivo para calcular el factorial de un número
2. public double factorial(int n){
3.     if (n==0)
4.         return 1;
5.     else
6.         return n*(factorial(n-1));
7. }

          Un método es recursivo cuando entre sus instrucciones se encuentra una llamada a sí mismo.Para entender el funcionamiento de la recursividad, podemos pensar que cada llamada supone hacerlo a un método diferente, copia del original, que se ejecuta y devuelve el resultado a quien lo llamó.

          En la figura siguiente podemos ver como sería la ejecución del programa Java anterior para calcular el factorial de 3. 

Un método recursivo debe contener:

•    Uno o más casos base: casos para los que existe una solución directa.
•    Una o más llamadas recursivas: casos en los que se llama sí mismo

          Caso base: Siempre ha de existir uno o más casos en los que los valores de los parámetros de entrada permitan al método devolver un resultado directo. Estos casos también se conocen como solución trivial del problema.

En el ejemplo del factorial el caso base es la condición:

if (n==0)

     return 1;

si n=0 el resultado directo es 1    No se produce llamada recursiva

          Llamada recursiva: Si los valores de los parámetros de entrada no cumplen la condición del caso base se llama recursivamente al método. En las llamadas recursivas el valor del parámetro en la llamada se ha de modificar de forma que se aproxime cada vez más hasta alcanzar al valor del caso base.

return n * ( factorial(n-1) );

por lo que en cada llamada el valor de n se acerca más a 0 que es el caso base.