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!

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 .

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

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

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.

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.

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

                                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

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.

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

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

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.

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

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.

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

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

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

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ą

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

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

}

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

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

Oto jedna linia rekurencyjna febonacciego:

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

Spróbuj tego

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

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

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

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

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

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

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

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

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