13,043,898 members (51,290 online)
alternative version

#### Stats

190.7K views
27 bookmarked
Posted 5 Nov 2007

# Iterative vs. Recursive Approaches

, 5 Nov 2007
 Rate this:
Implication of not thinking of iterative solutions over recursive from performance (response time) point of view

## Introduction

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

```//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;
}```
 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

```//--------------- 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<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

1. The calculations may be wrong in big numbers, however the algorithms should be correct.
2. For timer calculations, I used `System.Diagnostics.Stopwatch`.

## Points of Interest

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 memorization).

## History

• Post: November 06, 2007

## Share

 Software Developer (Senior) Taldor Israel
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.

## You may also be interested in...

 First Prev Next
 Nice Post Member 1120899119-Nov-14 6:58 Member 11208991 19-Nov-14 6:58
 It's a question of data structure virtuPIC15-Nov-07 20:45 virtuPIC 15-Nov-07 20:45
 blame C#, not .NET. F# does it better. Jay R. Wren13-Nov-07 2:00 Jay R. Wren 13-Nov-07 2:00
 Re: blame C#, not .NET. F# does it better. ncarey13-Nov-07 7:29 ncarey 13-Nov-07 7:29
 The problem is, as noted above, code generation, not recursion. Any recursive solution can be implemented via stack-based recursion. Computation of Fibonacci sequences and factorials are some of the classic examples of use for using recursion to solve a problem. However, they are (A) some of the most trivial of problems and (B) problems whose solution requires neither recursion nor a stack: using recursion to solve these problems is overkill. A good developer will construct his recursive solution, if possible, in such a manner that it is tail recursive. A good compiler will recognize a tail-recursive construct and optimize it into iteration. Tail Recursion is a special case of recursion where the last operation of the recursive function is the recursive call. Such a construct may be trivially (and automatically) converted to iteration (Tail Recursion Optimization). The reason for using recursion is clarity/simplicity of expression; not performance. Clarity and simplicity of expression mean that the code is (A) more maintainable and (B) less likely to contain bugs. Refusing to consider a recursive solution on peformance grounds is almost certainly a case of premature optimization. 90% of your performance problems will be in less than 10% of your codebase. Unless you have (A) a performance problem and (B) have identified its source, don't optimize. Strive instead for clarity of expression, simplicity and maintainability. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. -- Donald KnuthBottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is. -- Rob Pike
 Hum smesser6-Nov-07 5:06 smesser 6-Nov-07 5:06
 Re: Hum Eyal Lantzman6-Nov-07 20:08 Eyal Lantzman 6-Nov-07 20:08
 Good Job merlin9816-Nov-07 4:24 merlin981 6-Nov-07 4:24
 Good Best Practice The DevMan6-Nov-07 0:33 The DevMan 6-Nov-07 0:33
 Interesting norm .net5-Nov-07 21:46 norm .net 5-Nov-07 21:46
 Re: Interesting Eyal Lantzman5-Nov-07 22:32 Eyal Lantzman 5-Nov-07 22:32
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Jul-17 5:10 Refresh 1