Recursive Fibonacci code

Question

I have written the Fibonacci series as below. I would like to like to know if the below is the right way of using recursion because I am thinking I am looping the fibonacci function with the condition and incrementing value of i everytime just like a for loop.

public class FibanocciSeriesImpl {
static int a,b,i,n;
    static
    {
        a=0; b=1;i=2;
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of elements in the series");
        n=sc.nextInt();

    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("The fibnocci series is below");
        System.out.print(a+","+b);
        fibnocciImpl(a,b);
    }
    public static void fibnocciImpl(int a,int b)
    {
        int c=a+b;
        a=b;
        b=c;
        i++;
        System.out.print(","+c);
        if(i<n)
        fibnocciImpl(a,b);

    }
}

Answer 1

The fibonacci sequence can be implemented recursively in two lines of code, like so:

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

Please note this is not the most efficient way of calculating the fibonacci sequence, although this may be the most straightforward code-wise. I'll leave it to you to implement more efficiently.

Answer 2

Although this has been said many times, it's worth repeating: computing the Fibonacci sequence recursively---by the definition and without using, say, memoization---takes exponential time (something like O(1.6^n)), which is not feasible for large n (e.g. for n>40).

The Fibonacci sequence can also be computed iteratevly in linear time:

public static long fib(int n) {
    long a = 0, b = 1;
    if (n <= 1) { return n; }
    for (int i = 2; i < n; ++i) {
        int tmp = b;
        b += a;
        a = tmp;
    }
    return b;
}

For what it's worth, here's the same algorithm in Brainfuck (from my high school days :-):

++++++++++ > + ; N i j 
< ; point to N 
[
    > ; move pointer to i
    [ >> + > + <<< - ] ; add i to t1 and t2
    > ; move to j
    [ < + > - ] ; add j i 
    >> ; move to t2
    [ << + >> - ] ; add t2 to j 
    < ; move to t1
    [ >> + << - ] ; add t1 to t3
    >> ; move to t3 
    [ < + < + >> - ] ; move t3 to t1 and t2
    <<<<< -
]
>>> .

Answer 3

It is also possible to implement Fibonacci using Dynamic Programming which is much efficient than recursive.

int fibonacci(int n) {

    int[] f = new int[n + 1];
    int i;

    f[0] = 1;
    f[1] = 2;

    for (i = 2; i < n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    return f[i - 2];
}

Time Complexity: O(n) Extra Space: O(n)

Answer 4

You can do it in recursive like:

int fib(int i){
if(i == 0 || i ==1) return n;
else return fib(i - 1) + fib(i-2);
}

But the faster way is to do it with the iterativ way as you can read with examples here:

Iterative vs Recursive

Answer 5

Yes it's recursion, and no it's not recursion. :)

It's recursion because you are calling the function again, but you misused the recursion; you only replaced the loop with a recursive call.

Here is a simple example, to change the loop to recursion:

for(int i = 0; i < 3; i++) {
    // do something
}

Can be replaced by

  i = 0; // global variable
           //so that it maintains the value during recursive function calls
    void func() {
        // do something
        if(i < 3)
            func();
        i++;
    }

But good recursion is using the same function to do something meaningful.

Here is the beloved implementation for Fibonacci numbers:

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

Note how we made the function calculate itself by calling itself, and let the terminating condition do the magic! So when n = 0 or 1 it will return to the immediate caller with these numbers as a seed to the calculations.

So fib(1) = 1 and fib(2) = 2... and as we return back in the recursion stack, fib is being calculated.

Note that computing as a top down approach is exponential, but a down up approach whilst remembering the calculated fib (dynamic programming) is O(n), and is much more efficient way.

Answer 6

public static void printFIBO(int n) {
    System.out.println(n <=1 : n ? fib(n-1) + fib(n-2));
}