## 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