Java recursive Fibonacci sequence

Question

Please explain this simple 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);
}

I'm confused with the last line especially because if n = 5 for example, then fibonacci(4) + fibonacci(3) would be called and so on but I don't understand how this algorithm calculates the value at index 5 by this method. Please explain with a lot of detail!

Cribriform

Note that this is recursive and runs in exponential time. It's inefficient for large values of N. Using an iterative approach I was able to compute the first 10,000 numbers in the sequence. They can be found here - goo.gl/hnbF5 – Lues

@AdamFisher: Can you please share the code you used for computing 10,000 numbers in sequence ? I am actually curios to know it. – Crap

@AdamFisher The link you referred to is dead. – Nils

This video will explain to understand recursive function in 10 minuts youtube.com/watch?v=t4MSwiqfLaY – Abe

Please have a look at mine solution.That is optimized for recursive call I am bit surprised that nowhere this approach is mentioned on net – Bethesde

For future readers, here is the holy grail of tracing double recursion: youtube.com/watch?v=PT0mS3thy6Q&t=36s – Eld

There is also an Iterative approach which might be less difficult for you. Great article on both Recursive and Iterative with code here - codeflex.co/java-get-fibonacci-number-by-index – Jeanett

You should also return -1 if n is less than 0, or you will get an error. – Seersucker

@ChathuraPalihakkara That's a great video. Explaining recursion! – Deathwatch

Answer 1

In fibonacci sequence each item is the sum of the previous two. So, you wrote a recursive algorithm.

So,

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

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

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

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

Now you already know fibonacci(1)==1 and fibonacci(0) == 0. So, you can subsequently calculate the other values.

Now,

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

And from fibonacci sequence 0,1,1,2,3,5,8,13,21.... we can see that for 5th element the fibonacci sequence returns 5.

See here for Recursion Tutorial.

Tender

it will work but not optimized until and unless its optimized. Please have a look at mine answer. Let me know in case of suggestions/comments – Bethesde

Answer 2

There are 2 issues with your code:

1. The result is stored in int which can handle only a first 48 fibonacci numbers, after this the integer fill minus bit and result is wrong. But you never can run fibonacci(50).
2. The code fibonacci(n - 1) + fibonacci(n - 2) is very inefficient. The problem is that the it calls fibonacci not 50 times but much more.
   • At first it calls fibonacci(49)+fibonacci(48),
   • next fibonacci(48)+fibonacci(47) and fibonacci(47)+fibonacci(46)...
   • Each time it became fibonacci(n) worse, so the complexity is exponential:

The approach to non-recursive code:

 double fibonacci(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;
}

Archicarp

Although some of the other answers explain recursion more clearly, this is probably the most relevant answer at a deeper level. – Babbling

What does "integer fill minus bit" mean? – Quackery

@Quackery , it is about on how integer is stored. After int reached 2^31-1 the next bit is about sign, so the number become negative. – Archicarp

Much faster then recursive. The only reservation is that it won't work for n=1. Additional condition is needed – Horsewhip

Hey, just wondering how was your diagram to represent the recursive calls generated? – Submissive

@user2938375 it is a screenshot, but for Java profiling you can use VisualVM – Archicarp

I love the way you thought of a more relevant explanation, which i generally ignore. – Fishmonger

@chro This may be a better answer but it does not use a recursive function. – Schnur

"Each time it became 2^n worse" actually the number of total function calls is 2*fibonacci(n+1)-1, so it grows with the same complexity as the fibonacci numbers itself, which is 1.618^n instead of 2^n – Endres

I think answer should be corrected, double fibbonaci(int n){ double prev=0d, next=1d, result=0d; for (int i = 0; i < n-1; i++) { result=prev+next; prev=next; next=result; } return result; } – Berriman

For the second point about complexity, does it make a difference if the language supports tail call optimization? Or does that only affect the stack height and not the runtime? – Aftertaste

Answer 3

In pseudo code, where n = 5, the following takes place:

fibonacci(4) + fibonnacci(3)

This breaks down into:

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

This breaks down into:

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

This breaks down into:

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

This breaks down into:

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

This results in: 5

Given the fibonnacci sequence is 1 1 2 3 5 8 ..., the 5th element is 5. You can use the same methodology to figure out the other iterations.

Binghi

I think this answer explains the questions the best way. Really simple – Bandler

This is neat. Explains both the value at nth term and the series it follows. – Verbalism

Answer 4

You can also simplify your function, as follows:

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

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

Hersey

How is this any different than this or this or this answer? – Nunhood

It's just shorter and easier to read, which algorithms should always be =) – Hersey

@OtavioFerreira the only answer that has managed to solve my problem, good job – Ledaledah

Answer 5

Recursion can be hard to grasp sometimes. Just evaluate it on a piece of paper for a small number:

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

I am not sure how Java actually evaluates this, but the result will be the same.

Cotto

on the second line where does the 1 and 0 at the end come from? – Anemia

@Anemia fib(2) = fib(1) + fib(0) – Cotto

So you have fib (4) so n-1 and n-2 would be fib(3) + fib(2) then you do the n-1 and n-2 again you get -> fib(2) + fib(1), where have you got the + fib(1) + fib(0) from? Added onto the end – Anemia

@Anemia fib(2) + fib(1) is from fib(3), fib(1) + fib(0) is from fib(2) – Cotto

Answer 6

                                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)

Important point to note is this algorithm is exponential because it does not store the result of previous calculated numbers. eg F(n-3) is called 3 times.

For more details refer algorithm by dasgupta chapter 0.2

Gonzalogoo

There is a programming methodology by which we can avoid calculating F(n) for same n again and again using Dynamic Programming – Cacogenics

Answer 7

Most of the answers are good and explains how the recursion in fibonacci works.

Here is an analysis on the three techniques which includes recursion as well:

1. For Loop
2. Recursion
3. Memoization

Here is my code to test all three:

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

}

Here are the results:

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

Hence we can see memoization is the best time wise and for loop matches closely.

But recursion takes the longest and may be you should avoid in real life. Also if you are using recursion make sure that you optimize the solution.

Handyman

"Here we can see for loop is the best time wise"; "For Loop Time:347688"; "Memoization Time:327031"; 347688 > 327031. – Clothbound

@CodeConfident Yeah, I just saw that mistake today and was about to correct it. Thanks anyways :). – Handyman

Answer 8

This is the best video I have found that fully explains recursion and the Fibonacci sequence in Java.

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

This is his code for the sequence and his explanation is better than I could ever do trying to type it out.

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

Spit

Answer 9

For fibonacci recursive solution, it is important to save the output of smaller fibonacci numbers, while retrieving the value of larger number. This is called "Memoizing".

Here is a code that use memoizing the smaller fibonacci values, while retrieving larger fibonacci number. This code is efficient and doesn't make multiple requests of same function.

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

Blear

Answer 10

in the fibonacci sequence, the first two items are 0 and 1, each other item is the sum of the two previous items. i.e:
0 1 1 2 3 5 8...

so the 5th item is the sum of the 4th and the 3rd items.

Hoseahoseia

Answer 11

Michael Goodrich et al provide a really clever algorithm in Data Structures and Algorithms in Java, for solving fibonacci recursively in linear time by returning an array of [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;
    }
}

This yields fib(n) = fibGood(n)[0].

Previous

Answer 12

Here is 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's Fibonacci number formula used for above implementation. For large inputs long can be replaced with BigDecimal.

Lophobranch

Answer 13

Why this answer is different

Every other answer either:

• Prints instead of returns
• Makes 2 recursive calls per iteration
• Ignores the question by using loops

(aside: none of these is actually efficient; use Binet's formula to directly calculate the n^th term)

Tail Recursive Fib

Here is a recursive approach that avoids a double-recursive call by passing both the previous answer AND the one before that.

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

Clothbound

Answer 14

A Fibbonacci sequence is one that sums the result of a number when added to the previous result starting with 1.

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

Once we understand what Fibbonacci is, we can begin to break down the 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);
}

The first if statment checks for a base case, where the loop can break out. The else if statement below that is doing the same, but it could be re-written like so...

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

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

Now that a base case is establish we have to understand the call stack.Your first call to "fibonacci" will be the last to resolve on the stack (sequence of calls) as they resolve in the reverse order from which they were called. The last method called resolves first, then the last to be called before that one and so on...

So, all the calls are made first before anything is "calculated" with those results. With an input of 8 we expect an output of 21 (see table above).

fibonacci(n - 1) keeps being called until it reaches the base case, then fibonacci(n - 2) is called until it reaches the base case. When the stack starts summing the result in reverse order, the result will be like so...

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

They keep bubbling (resolving backwards) up until the correct sum is returned to the first call in the stack and that's how you get your answer.

Having said that, this algorithm is very inefficient because it calculates the same result for each branch the code splits into. A much better approach is a "bottom up" one where no Memoization (caching) or recursion (deep call stack) is required.

Like so...

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

Bumpy

Answer 15

Most of solutions offered here run in O(2^n) complexity. Recalculating identical nodes in recursive tree is inefficient and wastes CPU cycles.

We can use memoization to make fibonacci function run in O(n) time

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

If we follow Bottom-Up Dynamic Programming route, below code is simple enough to compute 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];
}

Mckay

Answer 16

It is a basic sequence that display or get a output of 1 1 2 3 5 8 it is a sequence that the sum of previous number the current number will be display next.

Try to watch link below Java Recursive Fibonacci sequence Tutorial

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

Click Here Watch Java Recursive Fibonacci sequence Tutorial for spoon feeding

Bitthia

What he needed to understand is how the code works and why it is written they way it is written. – Fourposter

I think i mention in my first sentence how it works? i write the code to make it more simple. btw, sorry. – Bitthia

Nothing wrong with your code. Only the guy wanted to understand how that code worked. Check the answer by RanRag. Something of that sort :) – Fourposter

ahh ok, sorry i am beginner here in stackoverflow. just want to help ^_^ – Bitthia

Answer 17

I think this is a simple way:

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

Auriscope

Answer 18

RanRag(accepted) answer will work fine but that's not optimized solution until and unless it is memorized as explained in Anil answer.

For recursive consider below approach, method calls of TestFibonacci are 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);
        }
    }

}

Bethesde

Answer 19

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

Beitz

Answer 20

By using an internal ConcurrentHashMap which theoretically might allow this recursive implementation to properly operate in a multithreaded environment, I have implemented a fib function that uses both BigInteger and Recursion. Takes about 53ms to calculate the first 100 fib numbers.

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

The test code is:

@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

Suzansuzann

Answer 21

Here is a one line febonacci recursive:

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

Cozza

Answer 22

I could not find a simple one liner with a ternary operator. So here is one:

public int fibonacci(int n) {
    return (n < 2) ? n : fibonacci(n - 2) + fibonacci(n - 1);
}

Prioress

Answer 23

Just to complement, if you want to be able to calculate larger numbers, you should use BigInteger.

An iterative example.

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

Franco

Answer 24

http://en.wikipedia.org/wiki/Fibonacci_number in more details

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

}

Make it that as simple as needed no need to use while loop and other loop

Safe

Answer 25

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

Oxheart

Answer 26

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

The advantage of this solution is that it's easy to read the code and understand it, hoping it helps

Tito

Answer 27

A Fibbonacci sequence is one that sums the result of a number then we have added to the previous result, we should started from 1. I was trying to find a solution based on algorithm, so i build the recursive code, noticed that i keep the previous number and i changed the position. I'm searching the Fibbonacci sequence from 1 to 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);
}

Raggedy

Answer 28

Try this

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

Heaton

Answer 29

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

Oreopithecus

Answer 30

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

Iquitos

Welcome to SO. While your answer does calculate the Fibonacci sequence. Your answer doesn't answer the OP, who asked about recursive functions. – Suck

Answer 31

Fibonacci series is one simple code that shows the power of dynamic programming. All we learned from school days is to run it via iterative or max recursive code. Recursive code works fine till 20 or so, if you give numbers bigger than that you will see it takes a lot of time to compute. In dynamic programming you can code as follows and it takes secs to compute the answer.

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

You store values in an array and proceed to fresh computation only when the array cannot provide you the answer.

Crocoite

Where is fib[] declared? What happens when negative value is passed for n? Did you mentioned fib type? Please test your code locally before posting it to StackOverflow. – Mckay

Answer 32

@chro is spot on, but s/he doesn't show the correct way to do this recursively. Here's the 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);
    }
}

Callus

Answer 33

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

Churchman

Answer 34

public class Fibonaci{      

    static void fibonacci() {
        int ptr1 = 1, ptr2 = 1, ptr3 = 0;
        int temp = 0;
        BufferedReader Data=new BufferedReader (new InputStreamReader(System.in));
        try {
            System.out.println("The Number Value's fib you required ? ");
            ptr3 = Integer.parseInt(Data.readLine());

            System.out.print(ptr1 + " " + ptr2 + " ");
            for (int i = 0; i < ptr3; i++) {
                System.out.print(ptr1 + ptr2 + " ");
                temp = ptr1;
                ptr1 = ptr2;
                ptr2 = temp + ptr2;
            }
        } catch(IOException err) {
            System.out.println("Error!" + err);
        } catch(NumberFormatException err) {
            System.out.println("Invald Input!");
        }
    }

    public static void main(String[]args)throws Exception{    
            Fibonaci.fibonacci();
    }   
 }

You can do like this.

Bonbon

Answer 35

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

    }
    }

Horotelic

Answer 36

Instead of using an array and doing some fancy things just two add two values is waste of time, I have found an efficient way to display/print,the famous Fibonacci sequence.

public static void main(String args[]){

        System.out.println("This program lists the Fibonacci sequence.");

        int answer = 0;
        int startValue = 1;
        int sum = 0;

        while (answer < 10000){

            System.out.println(answer);

            sum = add(answer,startValue);

            startValue = answer;
            answer = sum;               
        }   
    }
    //This method return the sum of addition 
    private static int add(int A,int B){
            return A+B;
    }

Soph

And the relevance of this answer (a loop) to the original question (explaining recursion) is? – Hebdomadary

Answer 37

Yes, it's important to memorize your calculated return value from each recursion method call, so that you can display the series in calling method.

There are some refinement in the implementation provided. Please find below implementation which gives us more correct and versatile output:

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

Output for number 50 is:

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

Langdon

I don't know who voted me down. However, tweak in the code to print complete Fib series. Fib series program problem statement does not only mean to display last number. Hope the down-voters would have understood the actual purpose of code. – Langdon