Recursividad En Java

Recursividad en Java

La recursividad es una técnica potente de programación que puede utilizarse en lugar de la iteración para resolver determinados tipos de problemas.

Por ejemplo, para escribir un método que calcule el factorial de un número entero no negativo, podemos hacerlo a partir de la definición de factorial:

0! = 1

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

si n>0

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

// Método Java no recursivo para calcular el factorial de un número

public double factorial(int n){

double fact=1;

int i;

if (n==0)

fact=1;

else

for(i=1;i<=n;i++)

fact=fact*i;

return fact;

}

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:

// Método Java recursivo para calcular el factorial de un número

public double factorial(int n){

if (n==0)

return 1;

else

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

}

Un método es recursivo cuando entre sus instrucciones se encuentra una llamada a sí mismo.

La solución iterativa es fácil de entender. Utiliza una variable para acumular los productos y obtener la solución. En la solución recursiva se realizan llamadas al propio método con valores de n cada vez más pequeños para resolver el problema.

Cada vez que se produce una nueva llamada al método se crean en memoria de nuevo las variables y comienza la ejecución del nuevo método.

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

...