Ejemplo 9 - Utilización de recursividad con varias invocaciones

Objetivo

Comprender el uso de recursividad con varios llamados recursivos

Enunciado

La serie matemática de Fibonacci es una de las más conocidas en su tipo. Esta serie se obtiene sumando los dos número anteriores de la siguiente forma:

1 1 2 3 5 8 13 21 34 55 etc...

Si se coloca un índice a partir de 0 para cada posición de los números se tiene que:

En otras palabras:

fibonacci(0) = 1

fibonacci(1) = 1

fibonacci(2) = 2

fibonacci(3) = 3

fibonacci(4) = 5

fibonacci(5) = 8

fibonacci(6) = 13

fibonacci(7) = 21

Escriba una función recursiva para calcular el número de fibonacci correspondiente a una posición específica dentro de la serie.


Solución

import javax.swing.JOptionPane;
public class Fibonacci{
public static int fibonacci(int indice){
if(indice<2)
return 1;
else
return (fibonacci(indice-1)+fibonacci(indice-2));
}
public static void main(String argv[]){
String cantidadString = JOptionPane.showInputDialog("Hasta que indice quiere ver la serie de Fibonacci?");
int cantidad = Integer.parseInt(cantidadString);
for(int i=0; i<cantidad;i++) {
System.out.println("Fibonacci de "+i+" es "+fibonacci(i));
}
System.exit(0);
}
}

Note que la condición de parada es cuando el índice vale 0 o 1. En otras palabras si es menor que 2.

En caso contrario hay dos llamados recursivos para calcular el fibonacci de la posicion anterior y el fibonacci de la posición transanterior. Estos van a ir recursivamente hasta obtener casos inmediatos donde devolverán valores iguales a 1. Al ir saliendo de la recursividad van a ir sumando los valores devueltos. Note que e primera instancia va a ir entrando por el lado izquierdo y al llegar a una condición de parada retorna al punto anterior donde en lugar de salir vuelve a entrar recursivamente en el segundo llamado de fibonacci. Una desventaja es que aunque ya haya calculado previamente el valor del fibonacci de un número al bajar por el lado izquierdo, estos valores intermedios se pierden al salir de la pila y tienen que volver a ser evaluados en el segundo llamado.

El siguiente es el caso para obtener los 10 primeros valores. Desde la posición 0 de la serie hasta la posición 9.

 

Produce la siguiente salida:

Código Fuente

Fibonacci.java