Introduction
This article was originally posted at blogs.microsoft.co.il/blogs/Eyal.
Recursive function – is a function that is 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 an iterative way and some may not.
Iterative functions – are loop based imperative repetitions of a process (in contrast to recursion which has a more declarative approach).
Comparison between Iterative and Recursive Approaches from Performance Considerations
Factorial
static int FactorialRecursive(int n)
{
if (n <= 1) return 1;
return n * FactorialRecursive(n - 1);
}
static int FactorialIterative(int n)
{
int sum = 1;
if (n <= 1) return sum;
while (n > 1)
{
sum *= n;
n--;
}
return sum;
}
N | Recursive | Iterative |
10 | 334 ticks | 11 ticks |
100 | 846 ticks | 23 ticks |
1000 | 3368 ticks | 110 ticks |
10000 | 9990 ticks | 975 ticks |
100000 | stack overflow | 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 ill level of each recursive call.
Fibonacci
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;
}
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
static Dictionary<int> resultHistory = new Dictionary<int>();
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;
}
N | Recursive | Recursive opt. | Iterative |
5 | 5 ticks | 22 ticks | 9 ticks |
10 | 36 ticks | 49 ticks | 10 ticks |
20 | 2315 ticks | 61 ticks | 10 ticks |
30 | 180254 ticks | 65 ticks | 10 ticks |
100 | too long/stack overflow | 158 ticks | 11 ticks |
1000 | too long/stack overflow | 1470 ticks | 27 ticks |
10000 | too long/stack overflow | 13873 ticks | 190 ticks |
100000 | too long/stack overflow | too long/stack overflow | 3952 ticks |
As before, the recursive approach is worse than iterative however, we could apply memorization pattern (saving previous results in dictionary for quick key based access), although this pattern isn't a match for the iterative approach (but definitely an improvement over the simple recursion).
Notes
- The calculations may be wrong in big numbers, however the algorithms should be correct.
- For timer calculations, I used
System.Diagnostics.Stopwatch
.
Points of Interest
- Try not to use recursion in system critical locations.
- Elegant solutions not always the best performing when used in "recursive situations".
- If you required to use recursion, at least try to optimize it with dynamic programming approaches (such as memorization).
History
In the last couple of years I'm working as Microsoft sub contractor in various project types - LOB, applications, CnC applications and Distributed applicaitons all of them considered to be extra large in tems of man power (or brain power), duration and geographic destribution between connected sites.