Rekurencyjna sekwencja Fibonacciego w Javie

156

Proszę wyjaśnić ten prosty kod:

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

Jestem zdezorientowany z ostatnią linią, zwłaszcza, że ​​jeśli na przykład n = 5, to zostanie wywołany fibonacci (4) + fibonacci (3) i tak dalej, ale nie rozumiem, jak ten algorytm oblicza wartość indeksu 5 przez to metoda. Proszę wyjaśnić szczegółowo!

Index Hacker
źródło
8
Zauważ, że jest to cykliczne i działa w czasie wykładniczym. Jest to nieefektywne dla dużych wartości N. Używając podejścia iteracyjnego, mogłem obliczyć pierwsze 10000 liczb w sekwencji. Można je znaleźć tutaj - goo.gl/hnbF5
Adam
@AdamFisher: Czy możesz udostępnić kod, którego użyłeś do obliczenia kolejno 10 000 liczb? Właściwie jestem ciekaw, żeby to wiedzieć.
Shumail,
4
@AdamFisher Odnośnik, o którym mowa, jest martwy.
iRuth
2
Ten film wyjaśni, jak zrozumieć funkcję rekurencyjną w 10 minut youtube.com/watch?v=t4MSwiqfLaY
Chathura Palihakkara
2
Istnieje również podejście iteracyjne, które może być dla Ciebie mniej trudne. Świetny artykuł na temat zarówno rekurencyjnego, jak i iteracyjnego z kodem tutaj - codeflex.co/java-get-fibonacci-number-by-index
user5495300

Odpowiedzi:

165

W sekwencji Fibonacciego każda pozycja jest sumą dwóch poprzednich. Więc napisałeś algorytm rekurencyjny.

Więc,

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

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

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

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

Teraz już wiesz fibonacci(1)==1 and fibonacci(0) == 0 . Możesz więc później obliczyć inne wartości.

Teraz,

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

A z sekwencji Fibonacciego 0,1,1,2,3,5,8,13,21....możemy zobaczyć, że dla 5th elementsekwencji Fibonacciego powraca 5.

Zobacz tutaj samouczek rekursji .

RanRag
źródło
będzie działać, ale nie będzie zoptymalizowany, dopóki nie zostanie zoptymalizowany. Proszę spojrzeć na moją odpowiedź. Daj mi znać w przypadku sugestii / komentarzy
M Sach
52

Z Twoim kodem są dwa problemy:

  1. Wynik jest przechowywany w int, który może obsłużyć tylko pierwsze 48 liczb Fibonacciego, po czym wypełnienie liczbą całkowitą minus bit i wynik jest nieprawidłowy.
  2. Ale nigdy nie możesz uruchomić Fibonacciego (50).
    Kod
    fibonacci(n - 1) + fibonacci(n - 2)
    jest bardzo zły.
    Problem w tym, że nazywa fibonacciego nie 50 razy, ale znacznie więcej.
    Na początku nazywa się fibonacci (49) + fibonacci (48),
    następnie fibonacci (48) + fibonacci (47) i fibonacci (47) + fibonacci (46)
    . wprowadź opis obrazu tutaj

Podejście do kodu nierekurencyjnego:

 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
źródło
4
Chociaż niektóre inne odpowiedzi wyjaśniają rekurencję jaśniej, jest to prawdopodobnie najbardziej odpowiednia odpowiedź na głębszym poziomie.
Hal50000
1
Co oznacza „wypełnienie całkowite minus bit”?
richard
1
@richard, chodzi o sposób przechowywania liczby całkowitej. Po tym, jak int osiągnął 2 ^ 31-1, następny bit dotyczy znaku, więc liczba staje się ujemna.
chro
Znacznie szybszy niż rekurencyjny. Jedyną rezerwacją jest to, że nie będzie działać dla n = 1. Potrzebny jest dodatkowy warunek
v0rin
1
„Za każdym razem, gdy stawało się 2 ^ n gorsze”, w rzeczywistości całkowita liczba wywołań funkcji wynosi 2*fibonacci(n+1)-1, więc rośnie z taką samą złożonością jak same liczby Fibonacciego, czyli 1,618 ^ n zamiast 2 ^ n
Aemyl
37

W pseudokodzie, gdzie n = 5, ma miejsce:

fibonacci (4) + fibonnacci (3)

To dzieli się na:

(Fibonacci (3) + Fibonnacci (2)) + (Fibonacci (2) + Fibonnacci (1))

To dzieli się na:

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

To dzieli się na:

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

To dzieli się na:

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

Skutkuje to: 5

Biorąc pod uwagę, że sekwencja Fibonnacciego to 1 1 2 3 5 8 ... , piątym elementem jest 5. Możesz użyć tej samej metodologii, aby znaleźć inne iteracje.

Dan Hardiker
źródło
Myślę, że ta odpowiedź najlepiej wyjaśnia pytania. Naprawdę proste
Amit
To jest fajne. Wyjaśnia zarówno wartość n-tego terminu, jak i następujący po niej szereg.
Średnik
12

Rekursja może być czasami trudna do uchwycenia. Po prostu oceń to na kartce papieru na małą liczbę:

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

Nie jestem pewien, jak Java to ocenia, ale wynik będzie taki sam.

tim
źródło
w drugiej linii, skąd pochodzi 1 i 0 na końcu?
pocockn
1
@pocockn fib (2) = fib (1) + fib (0)
tim
Więc masz fib (4), więc n-1 i n-2 to fib (3) + fib (2), a następnie ponownie wykonujesz n-1 i n-2, otrzymujesz -> fib (2) + fib (1) ), skąd masz + fib (1) + fib (0)? Dodano na koniec
pocockn
@pocockn fib (2) + fib (1) jest z fib (3), fib (1) + fib (0) jest z fib (2)
tim
12

Możesz również uprościć swoją funkcję w następujący sposób:

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

    return fibonacci(n - 1) + fibonacci(n - 2);
}
Otavio Ferreira
źródło
Czym to się różni od tej lub tej lub tej odpowiedzi?
Tunaki
6
Jest po prostu krótszy i łatwiejszy do odczytania, które algorytmy zawsze powinny być =)
Otavio Ferreira
@OtavioFerreira jedyna odpowiedź, która zdołała rozwiązać mój problem, dobra robota
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)

Należy zauważyć, że ten algorytm jest wykładniczy, ponieważ nie przechowuje wyników wcześniej obliczonych liczb. np. F (n-3) jest wywoływane 3 razy.

Więcej szczegółów można znaleźć w algorytmie opracowanym przez dasgupta w rozdziale 0.2

Amandeep Kamboj
źródło
Istnieje metodologia programowania, dzięki której możemy uniknąć
ciągłego
8

Większość odpowiedzi jest dobra i wyjaśnia, jak działa rekurencja w Fibonacciego.

Oto analiza trzech technik, która obejmuje również rekursję:

  1. Dla pętli
  2. Rekurencja
  3. Zapamiętywanie

Oto mój kod do przetestowania wszystkich trzech:

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

}

Oto wyniki:

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

Stąd widzimy, że memoizacja jest najlepsza pod względem czasu i ścisłego dopasowania pętli.

Jednak rekursja trwa najdłużej i być może powinieneś jej unikać w prawdziwym życiu. Również jeśli używasz rekurencji, upewnij się, że optymalizujesz rozwiązanie.

Pritam Banerjee
źródło
1
„Tutaj widzimy, że pętla for jest najlepsza pod względem czasu”; „For Loop Time: 347688”; „Czas zapamiętania: 327031”; 347688> 327031.
AjahnCharles
@CodeConfident Tak, właśnie zobaczyłem dzisiaj ten błąd i miałem go poprawić. W każdym razie dzięki :).
Pritam Banerjee,
7

To najlepszy film, jaki znalazłem, w pełni wyjaśniający rekurencję i ciąg Fibonacciego w Javie.

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

To jest jego kod sekwencji, a jego wyjaśnienie jest lepsze, niż mógłbym kiedykolwiek zrobić, próbując go wpisać.

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;
    }
user2718538
źródło
5

W przypadku rozwiązania rekurencyjnego Fibonacciego ważne jest, aby zapisać wyniki mniejszych liczb Fibonacciego, podczas pobierania wartości większej liczby. Nazywa się to „zapamiętywaniem”.

Oto kod, który używa zapamiętywania mniejszych wartości Fibonacciego, podczas pobierania większej liczby Fibonacciego. Ten kod jest wydajny i nie wysyła wielu żądań tej samej funkcji.

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
źródło
4

w sekwencji Fibonacciego pierwsze dwie pozycje to 0 i 1, każda inna pozycja jest sumą dwóch poprzednich pozycji. to znaczy:
0 1 1 2 3 5 8 ...

więc piąta pozycja to suma czwartej i trzeciej pozycji.

yurib
źródło
4

Michael Goodrich i wsp. Dostarczają naprawdę sprytnego algorytmu w Strukturach Danych i Algorytmach w Javie, do rekurencyjnego rozwiązywania fibonacciego w czasie liniowym poprzez zwracanie tablicy [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;
    }
}

To daje fib (n) = fibGood (n) [0].

Rae
źródło
4

Oto rozwiązanie 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);
}

Wzór na liczbę Fibonacciego Bineta użyty do powyższej implementacji. W przypadku dużych wejść longmożna zastąpić BigDecimal.

Samir
źródło
3

Sekwencja Fibbonacciego to taka, która sumuje wynik liczby po dodaniu do poprzedniego wyniku, zaczynając od 1.

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

Gdy zrozumiemy, czym jest Fibbonacci, możemy zacząć rozkładać kod.

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

Pierwsza instrukcja if sprawdza przypadek podstawowy, w którym może dojść do przerwania pętli. Poniższe oświadczenie else if robi to samo, ale można je przepisać w ten sposób ...

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

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

Teraz, gdy jest ustalony przypadek podstawowy, musimy zrozumieć stos wywołań. Twoje pierwsze wywołanie „fibonacci” będzie ostatnim, które zostanie rozstrzygnięte na stosie (sekwencja wywołań), ponieważ są one rozstrzygane w odwrotnej kolejności, z której zostały wywołane. Ostatnia wywoływana metoda jest najpierw rozwiązywana, potem ostatnia, która ma zostać wywołana przed nią i tak dalej ...

Tak więc wszystkie wywołania są wykonywane jako pierwsze, zanim cokolwiek zostanie „obliczone” na podstawie tych wyników. Przy wejściu 8 oczekujemy wyjścia 21 (patrz tabela powyżej).

Fibonacci (n - 1) jest wywoływana aż do przypadku podstawowego, a następnie Fibonacci (n - 2) jest wywoływana, aż osiągnie przypadek podstawowy. Kiedy stos zacznie sumować wynik w odwrotnej kolejności, wynik będzie taki ...

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

Ciągle bulgoczą (rozstrzygając wstecz) aż do momentu, gdy właściwa suma zostanie zwrócona do pierwszego sprawdzenia w stosie i w ten sposób otrzymasz odpowiedź.

Mimo to algorytm ten jest bardzo nieefektywny, ponieważ oblicza ten sam wynik dla każdej gałęzi, na którą dzieli się kod. Znacznie lepszym podejściem jest podejście „oddolne”, w którym nie jest wymagane zapamiętywanie (buforowanie) ani rekursja (głęboki stos wywołań).

Tak jak tak ...

        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
źródło
2

Większość oferowanych tutaj rozwiązań działa w złożoności O (2 ^ n). Ponowne obliczanie identycznych węzłów w drzewie rekurencyjnym jest nieefektywne i powoduje marnowanie cykli procesora.

Możemy użyć zapamiętywania, aby funkcja Fibonacciego działała w czasie 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];
}

Jeśli podążamy ścieżką programowania dynamicznego od dołu w górę, poniższy kod jest wystarczająco prosty, aby obliczyć fibonacciego:

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
źródło
2

Dlaczego ta odpowiedź jest inna

Każda inna odpowiedź:

  • Wydruki zamiast zwrotów
  • Tworzy 2 rekurencyjne wywołania na iterację
  • Ignoruje pytanie, używając pętli

(na marginesie: żadne z nich nie jest faktycznie wydajne; użyj wzoru Bineta, aby bezpośrednio obliczyć n- ty człon)

Ogon rekurencyjny Fib

Oto podejście rekurencyjne, które pozwala uniknąć podwójnego rekurencyjnego wywołania, przekazując zarówno poprzednią odpowiedź ORAZ poprzednią.

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
źródło
1

Jest to podstawowa sekwencja, która wyświetla lub uzyskuje wynik 1 1 2 3 5 8 jest to sekwencja, w której suma poprzedniej liczby zostanie wyświetlona jako następna.

Spróbuj obejrzeć link poniżej Samouczek dotyczący rekurencyjnej sekwencji Fibonacciego w Javie

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

Kliknij tutaj Obejrzyj samouczek dotyczący rekurencyjnej sekwencji Fibonacciego w języku Java dotyczący karmienia łyżeczką

Jaymelson Galang
źródło
Musiał zrozumieć, jak działa kod i dlaczego jest napisany tak, jak jest napisany.
Adarsh
Chyba w pierwszym zdaniu wspomnę, jak to działa? piszę kod, aby było prostsze. przy okazji, przepraszam.
Jaymelson Galang
Nie ma nic złego w Twoim kodzie. Tylko facet chciał zrozumieć, jak działa ten kod. Sprawdź odpowiedź RanRag. Coś w tym rodzaju :)
Adarsh
ahh ok, przepraszam, jestem początkującym tutaj w stackoverflow. po prostu chcę pomóc ^ _ ^
Jaymelson Galang
1

Myślę, że to prosty sposób:

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);
        }
    }
}
user3787713
źródło
1

Odpowiedź RanRag (zaakceptowana) będzie działać dobrze, ale nie jest to zoptymalizowane rozwiązanie, dopóki nie zostanie zapamiętane, jak wyjaśniono w odpowiedzi Anila.

W przypadku rekurencyjnego rozważania poniżej wywołania metod TestFibonaccisą minimalne

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
źródło
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
źródło
1

Używając wewnętrznej ConcurrentHashMap, która teoretycznie mogłaby pozwolić tej rekurencyjnej implementacji na prawidłowe działanie w środowisku wielowątkowym, zaimplementowałem funkcję Fib, która używa zarówno BigInteger, jak i Recursion. Obliczenie pierwszych 100 liczb Fib zajmuje około 53 ms.

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

Kod testu to:

@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));
}
a wynik testu to:
    .
    .
    .
    .
    .
    Fib z 93 to 12200160415121876738
    Fib z 94 to 19740274219868223167
    Fib z 95 to 31940434634990099905
    fib z 96 to 51680708854858323072
    Fib z 97 to 83621143489848422977
    Fib of 98 to 135301852344706746049
    Fib of 99 to 218922995834555169026
    Fib of 100 to 354224848179261915075
    upłynęło: 58,0
George Curington
źródło
1

Oto jedna linia rekurencyjna febonacciego:

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
RonTLV
źródło
1

Spróbuj tego

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
markus rytter
źródło
0

Dla uzupełnienia, jeśli chcesz mieć możliwość obliczania większych liczb, powinieneś użyć BigInteger.

Przykład iteracyjny.

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
źródło
0

http://en.wikipedia.org/wiki/Fibonacci_number więcej szczegółów

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

}

Uczyń to tak prostym, jak to konieczne, bez potrzeby używania pętli while i innych pętli

vikas
źródło
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;
    }
}
user3231661
źródło
0

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

Zaletą tego rozwiązania jest to, że łatwo jest odczytać kod i go zrozumieć, mając nadzieję, że pomoże

Gavriel Cohen
źródło
0

Ciąg Fibbonacciego to taki, który sumuje wynik liczby, którą dodaliśmy do poprzedniego wyniku, powinniśmy zacząć od 1. Próbowałem znaleźć rozwiązanie oparte na algorytmie, więc budowałem kod rekurencyjny, zauważyłem, że zachowuję poprzedni numer i zmieniłem pozycję. Przeszukuję ciąg Fibbonacciego od 1 do 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
źródło
-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
źródło
-1

Prosty Fibonacci

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
źródło
2
Witamy w SO. Podczas gdy twoja odpowiedź oblicza ciąg Fibonacciego. Twoja odpowiedź nie odpowiada OP, który pytał o funkcje rekurencyjne.
James K,
-2

@chro jest na miejscu, ale nie pokazuje poprawnego sposobu, aby to zrobić rekurencyjnie. Oto rozwiązanie:

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
źródło