Il y a 2 problèmes avec votre code:

1. Le résultat est stocké dans int qui ne peut gérer que les 48 premiers nombres de fibonacci, après quoi le nombre entier remplit moins le bit et le résultat est faux.
2. Mais vous ne pouvez jamais exécuter fibonacci(50).
   Le code
   fibonacci(n - 1) + fibonacci(n - 2)
   qui est très mauvais.
   Le problème est que le il appelle fibonacci pas 50 fois mais beaucoup plus.
   Au début, il appelle fibonacci(49)+fibonacci (48),
   à côté de fibonacci(48)+fibonacci(47) et fibonacci(47)+fibonacci(46)
   Chacun le temps qu'il est devenu fibonacci (n) pire, donc la complexité est exponentielle.

L'approche du code non récursif:

 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 pseudo-code, où n = 5, ce qui suit a lieu:

Fibonacci(4) + fibonnacci (3)

Cela se décompose en:

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

Cela se décompose en:

Si vous avez un problème, vous n'avez pas besoin de le faire.(0)) + 1))

Cela se décompose en:

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

Cela se décompose en:

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

Il en résulte: 5

Étant donné que la séquence de fibonnacci est 1 1 2 3 5 8 ..., le 5ème élément est 5. Vous pouvez utiliser la même méthodologie pour comprendre les autres itérations.

La récursivité peut parfois être difficile à saisir. Simplement évaluer sur un morceau de papier pour un petit nombre:

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

Je ne sais pas comment Java évalue réellement cela, mais le résultat sera le même.

                                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)

Point important à noter est que cet algorithme est exponentiel car il ne stocke pas le résultat des nombres calculés précédents. par exemple F(n-3) est appelé 3 fois.

Pour plus de détails, se reporter algorithme par dasgupta chapitre 0.2

C'est la meilleure vidéo que j'ai trouvée qui explique pleinement la récursivité et la séquence de Fibonacci en Java.

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

C'est son code pour la séquence et son explication est meilleure que je ne pourrais jamais le faire en essayant de la taper.

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

Pour une solution récursive de fibonacci, il est important de sauvegarder la sortie des nombres de fibonacci plus petits, tout en récupérant la valeur d'un nombre plus grand. Ceci est appelé "Memoizing".

Voici un code qui utilise mémoriser les plus petites valeurs de fibonacci, tout en récupérant un plus grand nombre de fibonacci. Ce code est efficace et ne fait pas plusieurs requêtes de la même fonction.

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

La plupart des réponses sont bonnes et expliquent comment fonctionne la récursivité dans fibonacci.

Voici une analyse sur les trois techniques qui inclut également la récursivité:

1. Pour La Boucle
2. la Récursivité
3. Mémorisation

Voici mon code pour tester les trois:

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

}

Voici les résultats:

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

Par conséquent, nous pouvons voir que la mémorisation est la meilleure en termes de temps et pour les correspondances en boucle de près.

Mais la récursivité prend le plus de temps et peut être que vous devriez éviter dans la vraie vie. De plus, si vous utilisez la récursivité, assurez-vous d'optimiser la solution.

Dans le fibonacci séquence, les deux premiers éléments sont 0 et 1, chaque autre élément est la somme des deux éléments précédents. c'est-à-dire:
0 1 1 2 3 5 8...

Donc le 5ème élément est la somme du 4ème et du 3ème éléments.

Michael Goodrich et al fournissent un algorithme vraiment intelligent dans les Structures de données et les algorithmes en Java, pour résoudre fibonacci récursivement en temps linéaire en renvoyant un tableau 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;
    }
}

Cela donne fib(n) = fibGood(n)[0].

Vous pouvez également simplifier votre fonction, comme suit:

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

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

Une séquence de Fibbonacci est une séquence qui somme le résultat d'un nombre lorsqu'elle est ajoutée au résultat précédent en commençant par 1.

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

Une fois que nous comprenons ce qu'est Fibbonacci, nous pouvons commencer à décomposer le code.

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

La première déclaration if vérifie un cas de base, où la boucle peut éclater. La déclaration else if ci-dessous fait la même chose, mais elle pourrait être réécrite comme ceci...

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

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

Maintenant qu'un cas de base est établi, nous devons comprendre la pile d'appels.Votre première l'appel à "fibonacci" sera le dernier à résoudre sur la pile (séquence d'appels) car ils se résolvent dans l'ordre inverse à partir duquel ils ont été appelés. La dernière méthode appelée résout en premier, puis la dernière à être appelée avant celle-ci et ainsi de suite...

Donc, tous les appels sont effectués en premier avant que tout ne soit "calculé" avec ces résultats. Avec une entrée de 8, nous nous attendons à une sortie de 21 (voir tableau ci-dessus).

Fibonacci(n - 1) continue d'être appelé jusqu'à ce qu'il atteigne le cas de base, puis fibonacci (n - 2) est appelé jusqu'à ce qu'il atteigne le cas de base. Lorsque la pile commence à additionner le résultat dans l'ordre inverse, le résultat sera comme ceci...

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

Ils continuent à bouillonner (résoudre en arrière) jusqu'à ce que la somme correcte soit renvoyée au premier appel de la pile et c'est ainsi que vous obtenez votre réponse.

Cela dit, cet algorithme est très inefficace car il calcule le même résultat pour chaque branche dans laquelle le code se divise. Une bien meilleure approche est une approche "bottom up" où aucun La mémorisation (mise en cache) ou la récursivité (pile d'appels profonds) est requise.

Comme ça...

        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 plupart des solutions proposées ici fonctionnent en complexité O(2^n). Recalculer des nœuds identiques dans l'arbre récursif est inefficace et gaspille des cycles CPU.

Nous pouvons utiliser la mémorisation pour faire fonctionner la fonction de fibonacci en O (n) temps

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 nous suivons la route de programmation dynamique Ascendante, le code ci-dessous est assez simple pour calculer 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];
}

C'est une séquence de base qui affiche ou obtient une sortie de 1 1 2 3 5 8 c'est une séquence que la somme du nombre précédent le nombre actuel sera affiché ensuite.

Essayez de regarder le lien ci-dessous Tutoriel de séquence de Fibonacci récursive Java

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

Cliquez Ici Montre Java Récursif de la suite de Fibonacci Tutoriel pour l'alimentation à la cuillère

Je pense que c'est un moyen 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 réponse RanRag(acceptée) fonctionnera bien mais ce n'est pas une solution optimisée jusqu'à ce qu'elle soit mémorisée comme expliqué dans une réponse Anil.

Pour l'approche récursive ci-dessous, les appels de méthode de TestFibonacci sont au minimum

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

}

Pourquoi cette réponse est différente

Toutes les autres réponses soit:

• Imprime au lieu de renvoie
• Effectue 2 appels récursifs par itération
• Ignore la question en utilisant des boucles

(mis à part: aucun d'entre eux n'est réellement efficace; utilisez La formule de Binet pour calculer directement le n ^term terme)

Fib récursif de queue

Voici une approche récursive qui évite un appel double récursif en passant à la fois la réponse précédente et l'avant.

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

En utilisant un ConcurrentHashMap interne qui peut théoriquement permettre cette implémentation récursive pour fonctionner correctement dans un multithread environnement, j'ai implémenté une fonction fib qui utilise à la fois BigInteger et la récursivité. Prend environ 53 ms pour calculer les 100 premiers nombres 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)));
    }
}

Le code de test est:

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

and output from the test is:
    .
    .
    .
    .
    .
    fib of 93 is 12200160415121876738
    fib of 94 is 19740274219868223167
    fib of 95 is 31940434634990099905
    fib of 96 is 51680708854858323072
    fib of 97 is 83621143489848422977
    fib of 98 is 135301852344706746049
    fib of 99 is 218922995834555169026
    fib of 100 is 354224848179261915075
    elapsed:58,0

Voici une récursive febonacci d'une ligne:

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

Juste pour compléter, si vous voulez pouvoir calculer des nombres plus grands, vous devez utiliser BigInteger.

Un exemple itératif.

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 plus de détails

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

}

Rendez - le aussi simple que nécessaire, pas besoin d'utiliser while loop et other loop

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

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

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

L'avantage de cette solution est qu'il est facile de lire le code et de le comprendre, en espérant qu'il contribue

Une suite de Fibbonacci est une suite qui somme le résultat d'un nombre puis nous avons ajouté au résultat précédent, nous devrions commencé à partir de 1. J'essayais de trouver une solution basée sur un algorithme, alors je construis le code récursif, j'ai remarqué que je conservais le numéro précédent et j'ai changé la position. Je recherche la séquence de Fibbonacci de 1 à 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;
}

La série Fibonacci est un code simple qui montre la puissance de la programmation dynamique. Tout ce que nous avons appris des jours d'école est de l'exécuter via un code récursif itératif ou max. Le code récursif fonctionne bien jusqu'à 20 ou plus, si vous donnez des nombres plus grands que cela, vous verrez qu'il faut beaucoup de temps pour calculer. En programmation dynamique, vous pouvez coder comme suit et il faut des secondes pour calculer la réponse.

static double fib(int n) {
    if (n < 2)
        return n;
    if (fib[n] != 0)
        return fib[n];
    fib[n] = fib(n - 1) + fib(n - 2);
    return fib[n];
}

Vous stockez des valeurs dans un tableau et procédez à un nouveau calcul uniquement lorsque le tableau ne peut pas fournir vous avez la réponse.

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

Oui, il est important de mémoriser votre valeur de retour calculée à partir de chaque appel de méthode de récursivité, afin que vous puissiez afficher la série dans la méthode d'appel.

Il y a un certain raffinement dans la mise en œuvre fournie. Veuillez trouver ci-dessous l'implémentation qui nous donne une sortie plus correcte et polyvalente:

import java.util.HashMap;
import java.util.stream.Collectors;

public class Fibonacci {
private static HashMap<Long, Long> map;

public static void main(String[] args) {
    long n = 50;
    map = new HashMap<>();
    findFibonacciValue(n);
    System.out.println(map.values().stream().collect(Collectors.toList()));
}

public static long findFibonacciValue(long number) {
    if (number <= 1) {
        if (number == 0) {
            map.put(number, 0L);
            return 0L;
        }
        map.put(number, 1L);
        return 1L;
    } else if (map.containsKey(number)) {
        return map.get(number);
    } else {
        long fibonacciValue = findFibonacciValue(number - 1L) + findFibonacciValue(number - 2L);
        map.put(number, fibonacciValue);
        return fibonacciValue;
    }
}
}

Sortie pour le nombre 50 est:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]

    import java.util.*;
/*
@ Author 12CSE54
@ Date 28.10.14
*/
    public class cfibonacci
    {
    public void print(int p)
    {
    int a=0,b=1,c;
    int q[]=new int[30];
    q[0]=a;
    q[1]=b;
    for(int i=2;i<p;i++)
    {
    c=a+b;
    q[i]=c;
    a=b;
    b=c;
    }
    System.out.println("elements are....\n");
    for(int i=0;i<q.length;i++)
    System.out.println(q[i]);
    }
    public static void main(String ar[])throws Exception
    {
    Scanner s=new Scanner(System.in);
    int n;
    System.out.println("Enter the number of elements\n");
    n=sc.nextInt();
    cfibonacci c=new cfibonacci();
    c.printf(n);

    }
    }