Fast Fibonacci recursion
algorithm, fibonacci, recursion
Solution
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..
Problem
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.