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