Fast Fibonacci recursion

Question

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 1

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

Answer 2

This kind of problems are linear recurrence types and they are solved fastest via fast matrix exponentiation. Here's the blogpost that describes this kind of approach concisely.