1

Buenas. Estoy tratando de dibujar la traza que sigue este codigo de fibonacci recursivo en Java para ver como funciona exactamente en este caso la recursividad. No acabo de entender el funcionamiento exacto en este caso concreto puesto que en el return se supone que se devuelve y se sale de la funcion en la que está pero en el return se entra recursivamente a 2 métodos que a su vez si no es 0 ni uno devuelve otra vez 2 metodos recursivos saliendo de ese metodo en cuestión.

El código es el siguiente:

public int fibonacci(int n) {

  if ((n == 0) || (n == 1)) // base cases
      return n;
    else
      // recursion step
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Alguien podría explicarme la traza que sigue el programa y en cada pasada el resultado de n al terminar cada función por cada vez que es llamada?

El return realmente hace que no haya un stack saliendo de la función y llamando a su vez a 2 funciones a modo de recursión de cola?

4
  • Puedes ir imprimiendo mensajes para ir viendo la traza tu mismo, no ?
    – lois6b
    Commented el 1 mar. 2017 a las 15:29
  • Que es lo que te falla realmente? Es un metodo un poco raro la verdad Commented el 1 mar. 2017 a las 15:30
  • @lois6b Lo que me rompe la cabeza es la parte de return fibonaaci(n-´1) + fibonacci(n-2);
    – Lorthas
    Commented el 1 mar. 2017 a las 15:32
  • @Lorthas si, la verdad es que es la primera vez que veo que se devuelva un metodo. Comprendo lo que intenta hacer, es como un procedimiento recursivo en pl/sql pero nose si en java es posible hacerlo Commented el 1 mar. 2017 a las 15:36

3 respuestas 3

5

Supongamos que ingresamos el número 3.

Como no es 0 ni 1 pasa al else {

Una vez dentro del else tenemos por seguro que el resultado sera la suma de fibonacci(n-1) + fibonacci(n-2), ejeplificando con un diagrama bien podría quedar de la siguiente forma

--------?(3)

------/------\

----?(2)------?(1)

Donde no sabemos el resultado "?" pero si el número que vamos a ingresar, se ejecuta el primer fibonacci del diagrama de la segunda linea fibonacci(n-1) que es fibonacci(2), al no ser 0 ni 1 pasa al else donde se ejecutará de nuevo fibonacci(n-1) + fibonacci(n-2), el diagrama nos quedaría ahora así

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-?(1)---?(0)

Ejecutando el primer fibonacci de la 3 linea fibonacci(n-1) que es 2 - 1 = 1 fibonacci(1), al ejecutarlo y ser 1, nos regresa n que es 1, entonces ya sabemos que regresa fibonacci(1)

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-1(1)---?(0)

Al ejecutar el segundo fibonnacci de la tercera linea fibonacci(n-2) que es 2 - 2 = 0 fibonacci(0) nos regresará 0, dado que regresa n y n

--------?(3)

------/------\

----?(2)------?(1)

--/----\

-1(1)---0(0)

Ahora sabemos que fibonacci(2) regresa fibonacci(1) + fibonacci(0) que es 1 + 0 = 1

--------?(3)

------/------\

----1(2)------?(1)

--/----\

-1(1)---?(0)

Pasamo al segundo fibonacci de la segunda linea que sabemos que fibonacci(1) = 1, entonces.

--------?(3)

------/------\

----1(2)------1(1)

--/----\

-1(1)---0(0)

Nuevamente sabemos que fibonacci(3) regresa fibonacci(2) + fibonacci(1) que es 1 + 1 =

--------2(3)

------/------\

----1(2)------1(1)

--/----\

-1(1)---0(0)

Pero como dijeron lo mejor sería debuggear o con simples prints te puede servir

2

Para entender el algoritmo, podemos empezar por los casos base e ir subiendo:

fibonacci(0) --> 0
fibonacci(1) --> 1

Para fibonacci(2) tenemos que aplicar la parte del else:

fibonacci(2) --> fibonacci(1) + fibonacci(0)

Para calcular la suma, hace falta conocer el resultado de las dos llamadas que, en el caso de suma, se evalúan de izquierda a derecha. Por tanto tenemos la siguiente secuencia:

fibonacci(2)
--> fibonacci(1) + fibonacci(0)
--> 1 + fibonacci(0)
--> 1 + 0
--> 1

Para fibonacci(3):

fibonacci(3)
--> fibonacci(2) + fibonacci(1)
--> (fibonacci(1) + fibonacci(0)) + fibonacci(1)
--> (1 + fibonacci(0)) + fibonacci(1)
--> (1 + 0) + fibonacci(1)
--> 1 + fibonacci(1)
--> 1 + 1
--> 2

Este último caso puedes observar que fibonacci(1) es invocado dos veces. Cuando mayor sea el número entero, más veces se repetirán los cálculos. (Un modo de optimización sería guardar el resultado para posteriores cálculos ("memoization")).

El proceso es bastante lineal, primero una función y luego la otra. No hay mezcla de stacks ya que las funciones no se invocan simultáneamente.

Haciendo un ejercicio de imaginación, para calcular fibonacci(n) no necesitas más de n niveles de recursividad, lo que es lo mismo, no más de n "stackframes".

0

Para ver la traza por ti mismo podrias usar el debugger de java o si no puedes mostrar en la consola lo que haces:

public int fibonacci(int n) {

  if ((n == 0) || (n == 1)) // base cases
       System.out.println("Devuelvo +"n)
       return n;
    else
       System.out.println("Entro en el else con +"n)      
        // recursion step
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Aunque puedes usar otros metodos para la serie fibonacci

public class fibonacci
{
public static void main (String[] args)
{
int a=0,b=1,c,hasta,i;
cantidad=15; //indica la cantidad de numeros en la serie fibonacci


for(i=0;i<hasta;i++)
{
c=a+b;
a=b;
b=c;
System.out.print(" "+a);
}
}

} 
10
  • con "Es un metodo un poco raro" te referias a que usa la recursion?
    – lois6b
    Commented el 1 mar. 2017 a las 15:36
  • Eso es, usa una recursion como si estubiera en un procedimiento recursivo de pl/sql nose si es posible en java Commented el 1 mar. 2017 a las 15:37
  • @lois6b Lo que intentaba precisamente es entender la recursión en todos sus casos, porque en casos simples se como funciona, pero en un caso más enrevesado como este me cuesta más verlo.
    – Lorthas
    Commented el 1 mar. 2017 a las 15:37
  • 1
    Solo mi opinión, pero esto me parece un largo comentario, mas bien que una respuesta a la pregunta.
    – sstan
    Commented el 1 mar. 2017 a las 15:38
  • 1
    @Lorthas yo tampoco comprendo muy bien como funciona esta recursion, lo que yo haria para comprender paso a paso como funciona es usar el debugger de java Commented el 1 mar. 2017 a las 15:45

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.