迭代 vs. 递归方法

• 下载源代码 - 2.5 KB

引言

这篇文章最初发布在 blogs.microsoft.co.il/blogs/Eyal。

递归函数 - 是一个部分由自身定义的函数，由一些已知答案的简单情况组成。示例：斐波那契数列，阶乘函数，快速排序等。
一些算法/函数可以用迭代方式表示，而有些可能不能。

迭代函数 - 是基于循环的，对过程的强制性重复（与具有更声明性方法的递归相反）。

从性能考虑的角度比较迭代和递归方法

阶乘

//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	递归	迭代语句
10	334 个时钟周期	11 个时钟周期
100	846 个时钟周期	23 个时钟周期
1000	3368 个时钟周期	110 个时钟周期
10000	9990 个时钟周期	975 个时钟周期
100000	堆栈溢出	9767 个时钟周期

我们可以清楚地看到，递归比迭代慢得多（相当多），并且有限制（堆栈溢出）。

性能差的原因是在每个递归调用的错误级别中大量推送-弹出寄存器。

斐波那契

//--------------- 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	递归	递归优化。	迭代语句
5	5 个时钟周期	22 个时钟周期	9 个时钟周期
10	36 个时钟周期	49 个时钟周期	10 个时钟周期
20	2315 个时钟周期	61 个时钟周期	10 个时钟周期
30	180254 个时钟周期	65 个时钟周期	10 个时钟周期
100	太长/堆栈溢出	158 个时钟周期	11 个时钟周期
1000	太长/堆栈溢出	1470 个时钟周期	27 个时钟周期
10000	太长/堆栈溢出	13873 个时钟周期	190 个时钟周期
100000	太长/堆栈溢出	太长/堆栈溢出	3952 个时钟周期

与之前一样，递归方法比迭代方法差，但是，我们可以应用记忆化模式（将先前的结果保存在字典中以进行快速的基于键的访问），尽管这种模式与迭代方法并不匹配（但绝对比简单的递归有所改进）。

注释

1. 在较大的数字中，计算结果可能不正确，但是算法应该是正确的。
2. 对于计时器计算，我使用了System.Diagnostics.Stopwatch。

关注点

1. 尽量不要在系统关键位置使用递归。
2. 优雅的解决方案在“递归情况”中使用时并不总是表现最佳。
3. 如果需要使用递归，至少尝试使用动态编程方法（例如记忆化）对其进行优化。

历史

• 发布时间：2007 年 11 月 06 日