Wednesday, January 2, 2013

Fibonacci Sequence With and Without Recursion


Fibonacci sequence is sequence with subsequent number is the sum of the previous two. See snapshot below from wikipedia.

We can implement this algorithm either using recursion or without. Let see both.Before the implementation let see how is the sequence defined for every F(n).

F(0) = 1 or F(0) = 0 in some definition
F(1) = 1
F(n) = F(n-1) + F(n-2)

Now these are implementation using Java

With Recursion
int fibo(int in){
 if(n <= 1){
  return n
 }else{
  return fibo(n-1) + fibo(n-2);
 }
}
Without Recursion
int fibo(int n){
 if(n <= 1){
  return n;
 }
 int fibo = 1;
 int fiboPrev = 1;
 for(int i = 2; i < n; ++i){
  int temp = fibo;
  fibo += fiboPrev;
  fiboPrev = temp;
 }
 return fibo;
}

3 comments:

  1. Hello,thanks for your code:)
    then I found a small mistake in your code.

    the code with Recursion
    int fibo(int in) → int n

    if(n <= 1){
    return n → miss a semicolon

    Thanks to your neat code!

    ReplyDelete
  2. Thanks for explaining this term! I am sure that I'll be able to easily follow the instruction!

    ReplyDelete
  3. Why the hell are you using recursion or a loop ? Since 17th century we can calculate Fibonacci for any value n using :
    lround((pow(0.5 + 0.5 * sqrt(5.0), n) -
    pow(0.5 - 0.5 * sqrt(5.0), n)) /
    sqrt(5.0))

    ReplyDelete