Fast Fibonacci recursion

algorithm recursion fibonacci
ducin picture ducin · Dec 11, 2012 · Viewed 50.5k times · Source

I'm trying to recall an algorithm on Fibonacci recursion. The following:

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

is not what I'm looking for because it's greedy. This will grow exponentially (just look at Java recursive Fibonacci sequence - the bigger the initial argument the more useless calls will be made).

There is probably something like a "cyclic argument shift", where calling previous Fibonacci value will retrieve value instead of calculating it again.

Answer

duedl0r picture duedl0r · Dec 11, 2012

maybe like this:

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}

this function is tail recursive. this means it could be optimized and executed very efficiently. In fact, it gets optimized into a simple loop..

Related questions

Why is the complexity of computing the Fibonacci series 2^n and not n^2?

I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n) worst case, cost of each level = cn, hence complexity = n*n=n^2 How come it is O(2^n)?

Read More
What is a good example of recursion other than generating a Fibonacci sequence?

Possible Duplicates: Real-world examples of recursion Examples of Recursive functions I see that most programming language tutorial teach recursion by using a simple example which is how to generate fibonacci sequence, my question is, is there another good example other …

Read More
What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

Read More