Iterative vs. Recursive Approaches

Eyal Lantzman, 5 Nov 2007 CPOL

 

 

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

Collapse | Copy Code

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

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

Collapse | Copy Code

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

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

转自：http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches

关于Tail Recursive

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

I would write the algorithm in the way that makes the most sense and is the most clear for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

转自： http://stackoverflow.com/questions/72209/recursion-or-iteration

参考资料：

尾调用：

http://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

http://en.wikipedia.org/wiki/Tail_call

【算法】转载：Iterative vs. Recursive Approaches