nike nike - 4 months ago 17
Java Question

Recursive Fibonacci code

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

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