This article will discuss the performance overhead when dealing with recursive problem-solving approaches.
Recursive functions – is a function that partially defined by itself and consists of some simple case with a known answer. Example: Fibonacci number sequence, factorial function, quick sort and more. Some of the algorithms/functions can be represented in iterative way and some may not.
Iterative functions – are loop based imperative repetition of a process (in contrast to recursion which has more declarative approach).
Comparison between Iterative and Recursive approaches from performance considerations
Factorial:
//recursive function calculates n!
static int FactorialRecursive(int n)
{
if (n <= 1) return 1;
return n * FactorialRecursive(n - 1);
}
//iterative function calculates n!
static int FactorialIterative(int n)
{
int sum = 1;
if (n <= 1) return sum;
while (n > 1)
{
sum *= n;
n--;
}
return sum;
}
Remark: in this test I don't look at the results because int isn't capable of holding such big numbers.
| N |
Recursive |
Iterative |
| 10 |
334 ticks |
11 ticks |
| 100 |
846 ticks |
23 ticks |
| 1000 |
3368 ticks |
110 ticks |
| 10000 |
9990 ticks |
975 ticks |
| 100000 |
stackoverflow |
9767 ticks |
As we can clearly see the recursive is a lot slower than the iterative (considerably) and limiting (stackoverflow).
The reason for the poor performance is heavy push-pop of the registers in the IL level of each recursive call.
Fibonacci:
//--------------- iterative version ---------------------
static int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
//--------------- naive recursive version ---------------------
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n - 1) +
FibonacciRecursive(n - 2);
}
//--------------- optimized recursive version ---------------------
static Dictionary resultHistory =
new Dictionary();
static int FibonacciRecursiveOpt(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (resultHistory.ContainsKey(n))
return resultHistory[n];
int result = FibonacciRecursiveOpt(n - 1) +
FibonacciRecursiveOpt(n - 2);
resultHistory[n] = result;
return result;
}
Remark: in this test I don't look at the results because int isn't capable of holding such big numbers.
| N |
Recursive |
Recursive opt. |
Iterative |
| 5 |
5 ticks |
22 ticks |
9 ticks |
| 10 |
36 ticks |
49 ticks |
10 ticks |
| 20 |
2315 ticks |
65 ticks |
10 ticks |
| 30 |
180254 ticks |
61 ticks |
9 ticks |
| 100 |
Too long/overflow |
158 ticks |
11 ticks |
| 1000 |
Too long/overflow |
1470 ticks |
27 ticks |
| 10000 |
Too long/overflow |
13873 ticks |
190 ticks |
| 100000 |
Too long/overflow |
Too long/overflow |
3952 ticks |
As before the recursive approach is worse than iterative however, we could apply memoization pattern (saving previous results in dictionary for quick key based access), although this pattern isn't match for iterative approach (but definitely improvement over the simple recursion).
1. Try not to use recursion in system critical locations
2. Elegant solutions not always the best performing when used in "recursive situations".
3. If you required to use recursion at least try to optimize it with dynamic programming approaches (such as memoization)
Source code @ CodeProject.com