Java récursif de la suite de Fibonacci

Dans la séquence de fibonacci chaque élément est la somme des deux précédents. Donc, vous avez écrit un algorithme récursif.

Donc,

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

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

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

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

Maintenant, vous savez déjà fibonacci(1)==1 and fibonacci(0) == 0. Ainsi, vous pouvez par la suite de calculer les autres valeurs.

Maintenant,

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

Et de la suite de fibonacci 0,1,1,2,3,5,8,13,21.... nous pouvons voir que pour 5th element la séquence de fibonacci retourne 5.

Voir ici pour La Récursivité Tutoriel.

En pseudo code, où n = 5, les événements suivants se produisent:

fibonacci(4) + fibonnacci(3)

Ce qui se décompose en:

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

Ce qui se décompose en:

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

Ce qui se décompose en:

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

Ce qui se décompose en:

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

Il en résulte: 5

Compte tenu de la fibonnacci séquence 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.

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

La plupart des réponses sont bonnes et explique comment la récursivité dans de fibonacci œuvres.

Ici est une analyse sur les trois techniques qui comprend la récursivité ainsi:

1. Pour La Boucle
2. La récursivité
3. Memoization

Voici mon code pour tester tous 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 memoization est le meilleur temps sage et pour la boucle correspond à près.

Mais la récursivité est la plus longue et peut-être que vous devez éviter dans la vie réelle. Aussi, si vous êtes en utilisant la récursivité assurez-vous d'optimiser la solution.

De fibonacci solution récursive, il est important d'enregistrer la sortie de plus petits nombres de fibonacci, lors de la récupération de la valeur du plus grand nombre. Ceci est appelé "Memoizing".

Voici un code qui utilisent memoizing la plus petite de fibonacci valeurs, tout en récupérant plus grand nombre de fibonacci. Ce code est efficace et n'est pas de faire de multiples demandes 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;
}
}
}

dans le fibonacci de la 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. j'.e:

0 1 1 2 3 5 8...

donc le 5ème élément est la somme de la 4e et la 3e éléments.

La plupart des solutions proposées ici s'exécuter en O(2^n) la complexité. Le recalcul des nœuds identiques récursive de l'arbre est inefficace et les déchets de cycles CPU.

Nous pouvons utiliser memoization pour faire fonction de fibonacci s'exécuter en O(n) le 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 Bottom-Up Dynamique de Programmation de la route, code ci-dessous est assez simple à 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 que l'affichage ou obtenir une sortie de
1 1 2 3 5 8
c'est une séquence que la somme du numéro précédent, le nombre actuel s'affiche à l'écran suivant.

Essayer de regarder le lien ci-dessous Java Récursif de la suite de Fibonacci Tutoriel

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

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

RanRag(accepté) réponse du bon travail, mais ce n'est pas une solution optimale jusqu'à ce que et à moins qu'il est mémorisé comme l'explique Anil réponse.

Récursive de considérer ci-dessous approche, les appels de méthode de TestFibonacci sont 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);
}
}
}

Ici est une ligne febonacci récursive:

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

http://en.wikipedia.org/wiki/Fibonacci_number dans 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));
}
}

Rendre aussi simple que de besoin pas besoin d'utiliser la boucle while et d'autres boucle de

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

Un Fibbonacci séquence est celle qui sommes le résultat d'un certain nombre
puis nous avons ajouté au résultat précédent, nous devrions commencé à partir de 1.
J'ai essayé de trouver une solution basée sur un algorithme, donc j'ai construit le code récursif, remarqué que je garde le numéro précédent, et j'ai changé la position. Je suis à la recherche de la Fibbonacci séquence 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);
}

Ici est O(1) solution :

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

Binet nombre de Fibonacci formule utilisé ci-dessus pour la mise en œuvre.
Pour les grandes entrées long peut être remplacé par BigDecimal.

La suite de Fibonacci est un code simple qui montre la puissance de la programmation dynamique. Tous nous avons appris de jours d'école est de le lancer via itératif ou max récursive code. Récursive code fonctionne très bien jusqu'à 20 ou alors, si vous donnez des nombres plus grands que ce que vous verrez, cela prend beaucoup de temps à calculer. La programmation dynamique, vous pouvez coder comme suit et il prend 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 stocker des valeurs dans un tableau et de procéder à la fraîche de calcul uniquement lorsque le tableau ne peut pas vous fournir la réponse.

Oui, il est important de mémoriser votre calculée valeur de retour de chaque récursion appel de méthode, de sorte que vous pouvez afficher la série en appelant la méthode.

Il y a une certaine amélioration dans la mise en œuvre prévue. Veuillez trouver ci-dessous la mise en œuvre, qui nous donne plus correcte et polyvalent de sortie:

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

De sortie pour le numéro 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]

@chro est sur place, mais il ne montre pas la manière correcte de le faire de manière récursive. Voici la solution:

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

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