If you are a programmer or computer science student, you must be aware of the Fibonacci sequence and how we calculate it using recursion. No?
Ok, then, let's see the typical recursive approach.
private static int headRecursion(int n){
if (n==1)
return 0;
if (n==2)
return 1;
else{
return headRecursion(n-1)+headRecursion(n-2);
}
}
Well, the above approach is not an ideal approach, wondering why? Because it has exponential time and space complexities.
Time Complexity: O(2^N) (Exponential Time Complexity)
N -> index of nth fibonacci number
Since every value is made up of the previous 2 values, we need to find 2 values for finding any Fibonacci number. This gives rise to 2 calls every time in our recursion tree. The tree can have at most n levels. This gives us at most 2^n nodes in the tree.
Space Complexity: O(2^N) (Exponential Space Complexity)
N -> index of nth fibonacci number
All the function calls are pushed into the function call stack. At any point in time at max 2^n, function calls are there in the call stack. Therefore, space complexity will be O(2^n)
Now, let's see the optimized recursive approach:
private static int tailRecursion(int n,int a,int b){
if (n==1)
return a;
if (n==2)
return b;
else{
return tailRecursion(n-1,b,a+b);
}
}
The initial values are a=0 and b=1. This is how we can optimally use recursion to find Fibonacci numbers!
In this case, there is just a single recursive function call which means that it is a faster approach - no need for two very similar recursive function calls (headRecursion(n-1) and headRecursion(n-2)). Java will not recalculate the same values several times.
Wondering what would be the time and space complexcities in this approach?
Time Complexity: O(N) (Linear Time Complexity)
N -> index of nth fibonacci number
For the nth number, there will be n function calls.
Space Complexity: O(1) (Constant Space Complexity), Isn't it amazing?
N -> index of nth fibonacci number
At any point in time, at max 1, function calls are there in the call stack. Therefore, space complexity will be O(1)
Do you like the article or have any suggestions? Please like and comment on the article.
Top comments (2)
Why would you want to take so much pain with recursion. You can do this with O(1) time with the following code. You can apply the same technique for a range or Nth fibonacci.
fib(n) = (Ψ ^n - (1 - Ψ)^n) / sqrt(5), where Ψ = 1.618This won't give you correct result after n=70.