nike - 1 year ago 121
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);

}
}
``````

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
<<<<< -
]
>>> .
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download