nike - 6 months ago 38

Java 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

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