Secuencia recursiva de Fibonacci de Java

156

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!

Index Hacker
fuente
8
Tenga en cuenta que esto es recursivo y se ejecuta en tiempo exponencial. Es ineficiente para valores grandes de N. Usando un enfoque iterativo pude calcular los primeros 10,000 números en la secuencia. Se pueden encontrar aquí - goo.gl/hnbF5
Adam
@AdamFisher: ¿Puedes compartir el código que usaste para calcular 10,000 números en secuencia? De hecho, tengo curiosidad por saberlo.
Shumail el
44
@AdamFisher El enlace al que te refieres está muerto.
iRuth
2
Este video explicará
cómo
2
También hay un enfoque iterativo que puede ser menos difícil para usted. Gran artículo tanto recursivo como iterativo con código aquí - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Respuestas:

165

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 .

RanRag
fuente
funcionará pero no estará optimizado hasta que esté optimizado. Por favor, eche un vistazo a mi respuesta. Avíseme en caso de sugerencias / comentarios
M Sach
52

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. ingrese la descripción de la imagen aquí

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;
}
chro
fuente
44
Aunque algunas de las otras respuestas explican la recursividad con mayor claridad, esta es probablemente la respuesta más relevante a un nivel más profundo.
Hal50000
1
¿Qué significa "relleno entero menos bit"?
richard
1
@richard, se trata de cómo se almacena el entero. Después de que int alcanzó 2 ^ 31-1, el siguiente bit es sobre el signo, por lo que el número se vuelve negativo.
chro
Mucho más rápido que recursivo. La única reserva es que no funcionará para n = 1. Se necesita condición adicional
v0rin
1
"Cada vez que se volvió 2 ^ n peor" en realidad es el número total de llamadas a funciones 2*fibonacci(n+1)-1, por lo que crece con la misma complejidad que los números de Fibonacci en sí, que es 1.618 ^ n en lugar de 2 ^ n
Aemyl
37

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.

Dan Hardiker
fuente
Creo que esta respuesta explica las preguntas de la mejor manera. Muy simple
Amit
Esto está bien. Explica tanto el valor en el enésimo término como la serie que sigue.
Punto
12

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.

tim
fuente
en la segunda línea, ¿de dónde vienen el 1 y el 0 al final?
pocockn
1
@pocockn fib (2) = fib (1) + fib (0)
tim
Entonces tienes fib (4), entonces n-1 y n-2 serían fib (3) + fib (2), luego haces n-1 y n-2 nuevamente y obtienes -> fib (2) + fib (1) ), ¿de dónde has obtenido el + fib (1) + fib (0)? Añadido al final
pocockn
@pocockn fib (2) + fib (1) es de fib (3), fib (1) + fib (0) es de fib (2)
tim
12

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);
}
Otavio Ferreira
fuente
¿Cómo es esto diferente de esto o esto o esta respuesta?
Tunaki
66
Es más corto y fácil de leer, qué algoritmos deberían ser siempre =)
Otavio Ferreira
@OtavioFerreira la única respuesta que ha logrado resolver mi problema, buen trabajo
KKKKK
8
                                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

Amandeep Kamboj
fuente
Existe una metodología de programación mediante la cual podemos evitar calcular F (n) para la misma n una y otra vez utilizando la Programación dinámica
Amit_Hora
8

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.

Pritam Banerjee
fuente
1
"Aquí podemos ver que el bucle es el mejor momento"; "Por tiempo de bucle: 347688"; "Tiempo de memorización: 327031"; 347688> 327031.
AjahnCharles
@CodeConfident Sí, acabo de ver ese error hoy y estaba a punto de corregirlo. Gracias de todos modos :).
Pritam Banerjee
7

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;
    }
usuario2718538
fuente
5

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;
    }
  }
}
Amarjit Datta
fuente
4

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.

yurib
fuente
4

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].

Rae
fuente
4

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.

Samir
fuente
3

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;
        }
Jeffrey Ferreiras
fuente
2

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];
}
realPK
fuente
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);
}
AjahnCharles
fuente
1

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

Jaymelson Galang
fuente
Lo que necesitaba entender es cómo funciona el código y por qué está escrito de la forma en que está escrito.
Adarsh
Creo que menciono en mi primera oración cómo funciona. Escribo el código para hacerlo más simple. Por cierto, lo siento.
Jaymelson Galang
No hay nada malo con tu código. Solo el chico quería entender cómo funcionaba ese código. Comprueba la respuesta de RanRag. Algo por el estilo :)
Adarsh
ahh ok, lo siento, soy un principiante aquí en stackoverflow. solo quiero ayudar ^ _ ^
Jaymelson Galang
1

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);
        }
    }
}
usuario3787713
fuente
1

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);
        }
    }

}
M. Sach
fuente
1
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]);
   }
 }
}
msanford
fuente
1

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
George Curington
fuente
1

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 );
}
RonTLV
fuente
1

Prueba esto

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

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("");
        }
    }
}
Tiago Zortea
fuente
0

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

vikas
fuente
0
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;
    }
}
usuario3231661
fuente
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

Gavriel Cohen
fuente
0

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);
}
Mathias Stavrou
fuente
-1
 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;
}
Ian Mukunya Douglas
fuente
-1

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;
    }
  }
}
Marcxcx
fuente
2
Bienvenido a SO. Mientras que su respuesta calcula la secuencia de Fibonacci. Su respuesta no responde al OP, que le preguntó sobre las funciones recursivas.
James K
-2

@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);
    }
}
taylordurden
fuente