Por favor explique este código simple:

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Estoy confundido con la última línea, especialmente porque si n = 5, por ejemplo, entonces se llamaría fibonacci (4) + fibonacci (3) y así sucesivamente, pero no entiendo cómo este algoritmo calcula el valor en el índice 5 por este método. ¡Por favor explique con muchos detalles!

En la secuencia de Fibonacci cada elemento es la suma de los dos anteriores. Entonces, escribiste un algoritmo recursivo.

Entonces,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Ahora ya lo sabes fibonacci(1)==1 and fibonacci(0) == 0. Entonces, puede calcular posteriormente los otros valores.

Ahora,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

Y a partir de la secuencia de Fibonacci 0,1,1,2,3,5,8,13,21....podemos ver que para 5th elementla secuencia de Fibonacci regresa 5.

Vea aquí el Tutorial de recursión .

Hay 2 problemas con su código:

1. El resultado se almacena en int, que puede manejar solo los primeros 48 números de Fibonacci, después de esto, el entero se llena menos bit y el resultado es incorrecto.
2. Pero nunca puedes correr fibonacci (50).
   El código
   fibonacci(n - 1) + fibonacci(n - 2)
   está muy mal.
   El problema es que no llama a Fibonacci 50 veces sino mucho más.
   Al principio se llama fibonacci (49) + fibonacci (48),
   luego fibonacci (48) + fibonacci (47) y fibonacci (47) + fibonacci (46)
   Cada vez se vuelve peor fibonacci (n), por lo que la complejidad es exponencial.

El enfoque del código no recursivo:

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}

En el pseudocódigo, donde n = 5, tiene lugar lo siguiente:

fibonacci (4) + fibonnacci (3)

Esto se descompone en:

(fibonacci (3) + fibonnacci (2)) + (fibonacci (2) + fibonnacci (1))

Esto se descompone en:

((((fibonacci (2) + fibonnacci (1)) + ((fibonacci (1) + fibonnacci (0))) + (((fibonacci (1) + fibonnacci (0)) + 1))

Esto se descompone en:

(((((fibonacci (1) + fibonnacci (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Esto se descompone en:

(((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Esto resulta en: 5

Dado que la secuencia de fibonnacci es 1 1 2 3 5 8 ... , el quinto elemento es 5. Puede usar la misma metodología para descubrir las otras iteraciones.

La recursión puede ser difícil de entender a veces. Simplemente evalúelo en una hoja de papel para un número pequeño:

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

No estoy seguro de cómo Java realmente evalúa esto, pero el resultado será el mismo.

También puede simplificar su función, de la siguiente manera:

public int fibonacci(int n)  {
    if (n < 2) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

                                F(n)
                                /    \
                            F(n-1)   F(n-2)
                            /   \     /      \
                        F(n-2) F(n-3) F(n-3)  F(n-4)
                       /    \
                     F(n-3) F(n-4)

Un punto importante a tener en cuenta es que este algoritmo es exponencial porque no almacena el resultado de números calculados previamente. por ejemplo, F (n-3) se llama 3 veces.

Para más detalles, consulte el algoritmo de dasgupta capítulo 0.2

La mayoría de las respuestas son buenas y explica cómo funciona la recursividad en fibonacci.

Aquí hay un análisis de las tres técnicas que también incluye la recursividad:

1. En bucle
2. Recursividad
3. Memorización

Aquí está mi código para probar los tres:

public class Fibonnaci {
    // Output = 0 1 1 2 3 5 8 13

    static int fibMemo[];

    public static void main(String args[]) {
        int num = 20;

        System.out.println("By For Loop");
        Long startTimeForLoop = System.nanoTime();
        // returns the fib series
        int fibSeries[] = fib(num);
        for (int i = 0; i < fibSeries.length; i++) {
            System.out.print(" " + fibSeries[i] + " ");
        }
        Long stopTimeForLoop = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));


        System.out.println("By Using Recursion");
        Long startTimeRecursion = System.nanoTime();
        // uses recursion
        int fibSeriesRec[] = fibByRec(num);

        for (int i = 0; i < fibSeriesRec.length; i++) {
            System.out.print(" " + fibSeriesRec[i] + " ");
        }
        Long stopTimeRecursion = System.nanoTime();
        System.out.println("");
        System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));



        System.out.println("By Using Memoization Technique");
        Long startTimeMemo = System.nanoTime();
        // uses memoization
        fibMemo = new int[num];
        fibByRecMemo(num-1);
        for (int i = 0; i < fibMemo.length; i++) {
            System.out.print(" " + fibMemo[i] + " ");
        }
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));

    }


    //fib by memoization

    public static int fibByRecMemo(int num){

        if(num == 0){
            fibMemo[0] = 0;
            return 0;
        }

        if(num ==1 || num ==2){
          fibMemo[num] = 1;
          return 1; 
        }

        if(fibMemo[num] == 0){
            fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
            return fibMemo[num];
        }else{
            return fibMemo[num];
        }

    }


    public static int[] fibByRec(int num) {
        int fib[] = new int[num];

        for (int i = 0; i < num; i++) {
            fib[i] = fibRec(i);
        }

        return fib;
    }

    public static int fibRec(int num) {
        if (num == 0) {
            return 0;
        } else if (num == 1 || num == 2) {
            return 1;
        } else {
            return fibRec(num - 1) + fibRec(num - 2);
        }
    }

    public static int[] fib(int num) {
        int fibSum[] = new int[num];
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                fibSum[i] = i;
                continue;
            }

            if (i == 1 || i == 2) {
                fibSum[i] = 1;
                continue;
            }

            fibSum[i] = fibSum[i - 1] + fibSum[i - 2];

        }
        return fibSum;
    }

}

Aquí están los resultados:

By For Loop
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:347688
By Using Recursion
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Recursion Time:767004
By Using Memoization Technique
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Memoization Time:327031

Por lo tanto, podemos ver que la memorización es el mejor momento y para las coincidencias de bucle de cerca.

Pero la recursión lleva más tiempo y es posible que deba evitarla en la vida real. Además, si está utilizando la recursividad, asegúrese de optimizar la solución.

Este es el mejor video que he encontrado que explica completamente la recursión y la secuencia de Fibonacci en Java.

http://www.youtube.com/watch?v=dsmBRUCzS7k

Este es su código para la secuencia y su explicación es mejor de lo que podría tratar de escribirlo.

public static void main(String[] args)
{
    int index = 0;
    while (true)
    {
        System.out.println(fibonacci(index));
        index++;
    }
}
    public static long fibonacci (int i)
    {
        if (i == 0) return 0;
        if (i<= 2) return 1;

        long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
        return fibTerm;
    }

Para la solución recursiva de Fibonacci, es importante guardar la salida de números de Fibonacci más pequeños, mientras se recupera el valor de un número mayor. Esto se llama "Memoizing".

Aquí hay un código que utiliza la memorización de los valores de Fibonacci más pequeños, mientras se recupera un número de Fibonacci más grande. Este código es eficiente y no realiza múltiples solicitudes de la misma función.

import java.util.HashMap;

public class Fibonacci {
  private HashMap<Integer, Integer> map;
  public Fibonacci() {
    map = new HashMap<>();
  }
  public int findFibonacciValue(int number) {
    if (number == 0 || number == 1) {
      return number;
    }
    else if (map.containsKey(number)) {
      return map.get(number);
    }
    else {
      int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
      map.put(number, fibonacciValue);
      return fibonacciValue;
    }
  }
}

En la secuencia de Fibonacci , los dos primeros elementos son 0 y 1, cada uno de los otros elementos es la suma de los dos elementos anteriores. es decir:
0 1 1 2 3 5 8 ...

entonces el quinto elemento es la suma de los elementos cuarto y tercero.

Michael Goodrich et al proporcionan un algoritmo realmente inteligente en estructuras de datos y algoritmos en Java, para resolver fibonacci recursivamente en tiempo lineal al devolver una matriz de [fib (n), fib (n-1)].

public static long[] fibGood(int n) {
    if (n < = 1) {
        long[] answer = {n,0};
        return answer;
    } else {
        long[] tmp = fibGood(n-1);
        long[] answer = {tmp[0] + tmp[1], tmp[0]};
        return answer;
    }
}

Esto produce fib (n) = fibGood (n) [0].

Aquí está la solución O (1):

 private static long fibonacci(int n) {
    double pha = pow(1 + sqrt(5), n);
    double phb = pow(1 - sqrt(5), n);
    double div = pow(2, n) * sqrt(5);

    return (long) ((pha - phb) / div);
}

Fórmula del número de Fibonacci de Binet utilizada para la implementación anterior. Para entradas grandes longse puede reemplazar con BigDecimal.

Una secuencia de Fibbonacci es una que suma el resultado de un número cuando se agrega al resultado anterior que comienza con 1.

      so.. 1 + 1 = 2
           2 + 3 = 5
           3 + 5 = 8
           5 + 8 = 13
           8 + 13 = 21

Una vez que comprendamos qué es Fibbonacci, podemos comenzar a descomponer el código.

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

El primero si la declaración comprueba un caso base, donde el bucle puede romperse. La otra declaración if a continuación está haciendo lo mismo, pero podría reescribirse así ...

    public int fibonacci(int n)  {
        if(n < 2)
             return n;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

Ahora que se establece un caso base, tenemos que entender la pila de llamadas. Su primera llamada a "fibonacci" será la última en resolverse en la pila (secuencia de llamadas) a medida que se resuelven en el orden inverso desde el que fueron llamadas. El último método llamado se resuelve primero, luego el último llamado antes de ese y así sucesivamente ...

Por lo tanto, todas las llamadas se realizan primero antes de que algo se "calcule" con esos resultados. Con una entrada de 8, esperamos una salida de 21 (ver tabla anterior).

fibonacci (n - 1) se sigue llamando hasta que alcanza el caso base, luego se llama fibonacci (n - 2) hasta que alcanza el caso base. Cuando la pila comienza a sumar el resultado en orden inverso, el resultado será así ...

1 + 1 = 1        ---- last call of the stack (hits a base case).
2 + 1 = 3        ---- Next level of the stack (resolving backwards).
2 + 3 = 5        ---- Next level of the stack (continuing to resolve).

Siguen burbujeando (resolviendo hacia atrás) hasta que se devuelve la suma correcta a la primera llamada en la pila y así es como obtienes tu respuesta.

Dicho esto, este algoritmo es muy ineficiente porque calcula el mismo resultado para cada rama en la que se divide el código. Un enfoque mucho mejor es uno "de abajo hacia arriba" donde no se requiere Memoization (almacenamiento en caché) o recursividad (stack de llamadas profundas).

Al igual que...

        static int BottomUpFib(int current)
        {
            if (current < 2) return current;

            int fib = 1;
            int last = 1;

            for (int i = 2; i < current; i++)
            {
                int temp = fib;
                fib += last;
                last = temp;
            }

            return fib;
        }

La mayoría de las soluciones ofrecidas aquí se ejecutan en complejidad O (2 ^ n). Recalcular nodos idénticos en el árbol recursivo es ineficiente y desperdicia ciclos de CPU.

Podemos usar la memorización para hacer que la función fibonacci se ejecute en tiempo O (n)

public static int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

public static int fibonacci(int i, int[] memo) {

    if (i == 0 || i == 1) {
        return i;
    }

    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

Si seguimos la ruta de programación dinámica de abajo hacia arriba, el siguiente código es lo suficientemente simple como para calcular fibonacci:

public static int fibonacci1(int n) {
    if (n == 0) {
        return n;
    } else if (n == 1) {
        return n;
    }
    final int[] memo = new int[n];

    memo[0] = 0;
    memo[1] = 1;

    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}

¿Por qué esta respuesta es diferente?

Cualquier otra respuesta:

• Imprime en lugar de devoluciones
• Realiza 2 llamadas recursivas por iteración.
• Ignora la pregunta usando bucles

(aparte: ninguno de estos es realmente eficiente; use la fórmula de Binet para calcular directamente el ^enésimo término)

Cola recursiva fib

Aquí hay un enfoque recursivo que evita una llamada doble recursiva al pasar tanto la respuesta anterior como la anterior.

private static final int FIB_0 = 0;
private static final int FIB_1 = 1;

private int calcFibonacci(final int target) {
    if (target == 0) { return FIB_0; }
    if (target == 1) { return FIB_1; }

    return calcFibonacci(target, 1, FIB_1, FIB_0);
}

private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
    final int current = previous + 1;
    final int fibCurrent = fibPrevious + fibPreviousMinusOne;
    // If you want, print here / memoize for future calls

    if (target == current) { return fibCurrent; }

    return calcFibonacci(target, current, fibCurrent, fibPrevious);
}

Es una secuencia básica que muestra u obtiene una salida de 1 1 2 3 5 8 es una secuencia que la suma del número anterior el número actual se mostrará a continuación.

Intenta ver el enlace a continuación Tutorial de la secuencia de Fibonacci recursiva de Java

public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}

Haga clic aquí Vea el tutorial de secuencia recursiva de Fibonacci de Java para la alimentación con cuchara

Creo que esta es una manera simple:

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        long a = 0;
        long b = 1;
        for(int i = 1; i<number;i++){
            long c = a +b;
            a=b;
            b=c;
            System.out.println(c);
        }
    }
}

La respuesta RanRag (aceptada) funcionará bien, pero esa no es una solución optimizada hasta que se memorice como se explica en la respuesta de Anil.

Para el enfoque recursivo, considere el siguiente enfoque, las llamadas a métodos TestFibonaccison mínimas

public class TestFibonacci {

    public static void main(String[] args) {

        int n = 10;

        if (n == 1) {
            System.out.println(1);

        } else if (n == 2) {
            System.out.println(1);
            System.out.println(1);
        } else {
            System.out.println(1);
            System.out.println(1);
            int currentNo = 3;
            calFibRec(n, 1, 1, currentNo);
        }

    }

    public static void calFibRec(int n, int secondLast, int last,
            int currentNo) {
        if (currentNo <= n) {

            int sum = secondLast + last;
            System.out.println(sum);
            calFibRec(n, last, sum, ++currentNo);
        }
    }

}

public class febo 
{
 public static void main(String...a)
 {
  int x[]=new int[15];  
   x[0]=0;
   x[1]=1;
   for(int i=2;i<x.length;i++)
   {
      x[i]=x[i-1]+x[i-2];
   }
   for(int i=0;i<x.length;i++)
   {
      System.out.println(x[i]);
   }
 }
}

Al usar un ConcurrentHashMap interno que teóricamente podría permitir que esta implementación recursiva funcione correctamente en un entorno multiproceso, he implementado una función fib que usa BigInteger y Recursion. Toma alrededor de 53 ms para calcular los primeros 100 números de fib.

private final Map<BigInteger,BigInteger> cacheBig  
    = new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
    BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
    return a;
}
public BigInteger fibBigCache(BigInteger n) {
    if ( n.compareTo(BigInteger.ONE ) <= 0 ){
        return n;
    } else if (cacheBig.containsKey(n)){
        return cacheBig.get(n);
    } else {
        return      
            fibBigCache(n.subtract(BigInteger.ONE))
            .add(fibBigCache(n.subtract(TWO)));
    }
}

El código de prueba es:

@Test
public void testFibRecursiveBigIntegerCache() {
    long start = System.currentTimeMillis();
    FibonacciSeries fib = new FibonacciSeries();
    IntStream.rangeClosed(0,100).forEach(p -&R {
        BigInteger n = BigInteger.valueOf(p);
        n = fib.fibRecursiveBigCache(n);
        System.out.println(String.format("fib of %d is %d", p,n));
    });
    long end = System.currentTimeMillis();
    System.out.println("elapsed:" + 
    (end - start) + "," + 
    ((end - start)/1000));
}

y la salida de la prueba es:
    .
    .
    .
    .
    .
    fib de 93 es 12200160415121876738
    fib de 94 es 19740274219868223167
    fib de 95 es 31940434634990099905
    fib de 96 es 51680708854858323072
    fib de 97 es 83621143489848422977
    fib de 98 es 135301852344706746049
    fib de 99 es 218922995834555169026
    fib de 100 es 354224848179261915075
    transcurrido: 58,0

Aquí hay un recursivo febonacci de una línea:

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}

Prueba esto

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Solo para complementar, si desea poder calcular números más grandes, debe usar BigInteger.

Un ejemplo iterativo.

import java.math.BigInteger;
class Fibonacci{
    public static void main(String args[]){
        int n=10000;
        BigInteger[] vec = new BigInteger[n];
        vec[0]=BigInteger.ZERO;
        vec[1]=BigInteger.ONE;
        // calculating
        for(int i = 2 ; i<n ; i++){
            vec[i]=vec[i-1].add(vec[i-2]);
        }
        // printing
        for(int i = vec.length-1 ; i>=0 ; i--){
            System.out.println(vec[i]);
            System.out.println("");
        }
    }
}

http://en.wikipedia.org/wiki/Fibonacci_number en más detalles

public class Fibonacci {

    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }

}

Haga que sea tan simple como sea necesario, no es necesario usar el bucle while y el otro bucle

public class FibonacciSeries {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        for (int i = 0; i <= N; i++) {
            int result = fibonacciSeries(i);
            System.out.println(result);
        }
        scanner.close();
    }

    private static int fibonacciSeries(int n) {
        if (n < 0) {
            return 1;
        } else if (n > 0) {
            return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
        }
        return 0;
    }
}

Uso while:

public int fib(int index) {
    int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
    while (tmp < index - 1) {
        fibNumber = step1 + step2;
        step1 = step2;
        step2 = fibNumber;
        tmp += 1;
    };
    return fibNumber;
}

La ventaja de esta solución es que es fácil leer el código y comprenderlo, esperando que ayude

Una secuencia de Fibbonacci es una que suma el resultado de un número que luego hemos agregado al resultado anterior, deberíamos comenzar desde 1. Estaba tratando de encontrar una solución basada en un algoritmo, así que construí el código recursivo, noté que mantengo el número anterior y cambié la posición. Estoy buscando la secuencia de Fibbonacci del 1 al 15.

public static void main(String args[]) {

    numbers(1,1,15);
}


public static int numbers(int a, int temp, int target)
{
    if(target <= a)
    {
        return a;
    }

    System.out.print(a + " ");

    a = temp + a;

    return numbers(temp,a,target);
}

 public static long fib(int n) {
    long population = 0;

    if ((n == 0) || (n == 1)) // base cases
    {
        return n;
    } else // recursion step
    {

        population+=fib(n - 1) + fib(n - 2);
    }

    return population;
}

Fibonacci simple

public static void main(String[]args){

    int i = 0;
    int u = 1;

    while(i<100){
        System.out.println(i);
        i = u+i;
        System.out.println(u);
        u = u+i;
    }
  }
}

@chro es perfecto, pero no muestra la forma correcta de hacerlo de forma recursiva. Aquí está la solución:

class Fib {
    static int count;

    public static void main(String[] args) {
        log(fibWrong(20));  // 6765
        log("Count: " + count); // 21891
        count = 0;
        log(fibRight(20)); // 6765
        log("Count: " + count); // 19
    }

    static long fibRight(long n) {
        return calcFib(n-2, 1, 1);
    }

    static long fibWrong(long n) {
        count++;
        if (n == 0 || n == 1) {
            return n;
        } else if (n < 0) {
            log("Overflow!");
            System.exit(1);
            return n;
        } else {
            return fibWrong(n-1) + fibWrong(n-2);
        }

    }

    static long calcFib(long nth, long prev, long next) {
        count++;
        if (nth-- == 0)
            return next;
        if (prev+next < 0) {
            log("Overflow with " + (nth+1) 
                + " combinations remaining");
            System.exit(1);
        }
        return calcFib(nth, next, prev+next);
    }

    static void log(Object o) {
        System.out.println(o);
    }
}