When Recursion Goes Wrong

When I was in college, my text book used a Fibonacci example to explain how recursion worked. Later on the job I needed to write a program in recursion. After the program ran eight to nine hours, my machine ran out of memory. It was a case of recursion went wrong. In fact, it can go very wrong sometimes. What I was taught in school to use recursion to solve Fibonacci problem is a classic example of bad recursion.

Bad recursion can increase runtime in an exponential number

Recursion can be very powerful is by using its ‘divide and conquer’ strategy. A recursion with good algorithm can cut the run time to a fraction of the time when only use for loops.

But since recursion breaks the problem into sub problems, the number of sub problems can increase in an exponential number, thus make runtime to increase explosively. How can this happen? Let’s look at Fibonacci in recursion.

Fibonacci function:

1. fib(0)=1
2. fib(1)=1
3. fib(n)=fib(n-1) + fib(n-2) (n>=2)

The recursive implementation of Fibonacci function:

int fib( int n) {
if( n <= 1)
return 1;
else
return fib(n – 1) + fib(n – 2);
}

This is a classic example of recursion going horrible wrong. If we look carefully, it does repetitive work of recursive calling without using the sum from sub problem.

N=2, fib(2) = fib (1)+ fib(0) 2 calls to compute fib(1) and fib(0)

N=3, fib(3) = fib(2) + fib(1) 2 separate calls to compute fib(2) and fib(1), in which fib(2) = fib(1) + fib(0) . fib(1) is called 2 times. fib(0) 1 time.

N=4, fib(4) = fib(3) + fib(2).
Separate calls to compute fib(3) and fib(2). fib(3) =fib(2)+fib(1).
fib(3) is called 1 time, fib(2) is called2 times, fib(1)
is called 3 times and fib(0) is called 2 times.

N=5, fib(5) = fib(4) + fib(3), fib(4) is called once, fib(3) is called twice, fib(2) is called 3 times, fib(1) is called 5 times, fib(0) is called 3 times.

……

N=n, f(n) = f(n-1) + f(n-2), f(n-1) is called 1 time, f(n-2) is called 2 times, f(n-3) is called 3 times, f(n-4) is called 5 times.

How to fix the problem

The problem of the explosive calls in this recursion method is caused by recursive method spawns separate calls without reusing the computing results from the subproblem. To calculate fib(n) = fib (n-1) + fib(n-2), we can calculate from the base condition and use the sum when we go forward:

fib(0)=1;
fib(1)=1;
fib(2) = f(1) + f(0) = 1+1= 2;
fib(3)= f(2) +f(1) = 2+1= 3;
fib(4)= f(3) +f(2) = 3+2= 5;
……

int fib( int n ){
//base condition f(0)=1, f(1)=1
fibPrev =1;
fibNext=1;
if(n<2){
return 1;
}
/*if n>=2, we will compute the sub problem first and
use the sum for further computation*/
for(int i =2;i<=n;i ++)
{
fibSum = fibNext+fibPre ;
fibPre = fibNext ;
fibNext = fibSum;
}
return fibSum ;
}

So the above implementation illustrates that the problem can be solved by using for loop instead of using recursion. The for loop is a constant running time with O(n), compared to what is an exponential growth in recursion
scenario.

Summary

Sometimes a problem seems to be a perfect fit for recursion can actually be solved by a simple for loop solution with better performance. When the result from the sub problem is not used efficiently by the recursion call stack and computation is done redundantly, the running time can grow explosively. This is when the recursion can go horribly wrong.