漫谈递归：递归的效率问题

递归在解决某些问题的时候使得我们思考的方式得以简化，代码也更加精炼，容易阅读。那么既然递归有这么多的优点，我们是不是什么问题都要用递归来解决呢？难道递归就没有缺点吗？今天我们就来讨论一下递归的不足之处。谈到递归就不得不面对它的效率问题。

为什么递归是低效的

还是拿斐波那契（Fibonacci）数列来做例子。在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数（不考虑参数小于1或结果溢出等异常情况），我不知你的程序是否会和下列代码类似：

public static ulong Fib(ulong n)
{
    return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
}

这段代码应该算是短小精悍（执行代码只有一行），直观清晰，而且非常符合许多程序员的代码美学，许多人在面试时写出这样的代码可能心里还会暗爽。但是如果用这段代码试试计算Fib(1000)我想就再也爽不起来了，它的运行时间也许会让你抓狂。

看来好看的代码未必中用，如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例：

从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。

我们当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。

改进的斐波那契递归算法

那么计算斐波那契数列是否有更好的递归算法呢？ 当然有。让我们来观察一下斐波那契数列的前几项：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

注意到没有，如果我们去掉前面一项，得到的数列依然满足f(n) = f(n-1) – f(n-2), (n>2)，而我们得到的数列是以1，2开头的。很容易发现这个数列的第n-1项就是原数列的第n项。怎么样，知道我们该怎么设计算法了吧？我们可以写这样的一个函数，它接受三个参数，前两个是数列的开头两项，第三个是我们想求的以前两个参数开头的数列的第几项。

int fib_i(int a, int b, int n);

在函数内部我们先检查n的值，如果n为3则我们只需返回a+b即可，这是简单情境。如果n>3，那么我们就调用f(b, a+b, n-1)，这样我们就缩小了问题的规模（从求第n项变成求第n-1项）。好了，最终代码如下：

int fib_i(int a, int b , int n)
{
    if(n == 3)
        return a+b;
    else
        return fib_i(b, a+b, n-1);
}

这样得到的算法复杂度是O(n)的。已经是线性的了。它的效率已经可以与迭代算法的效率相比了，但由于还是要反复的进行函数调用，还是不够经济。

递归与迭代的效率比较

我们知道，递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。

这样，我们发现，同一个问题，如果递归解决方案的复杂度不明显优于其它解决方案的话，那么使用递归是不划算的。因为它的很多时间浪费在对函数调用的处理上。在C++中引入了内联函数的概念，其实就是为了避免简单函数内部语句的执行时间小于函数调用的时间而造成效率降低的情况出现。在这里也是一个道理，如果过多的时间用于了函数调用的处理，那么效率显然高不起来。

举例来说，对于求阶乘的函数来说，其迭代算法的时间复杂度为O(n)：

int fact(n)
{
    int i;
    int r = 1;
    for(i = 1; i <= n; i++)
    {
        r *= i;
    }
    return r;
}

而其递归函数的时间复杂度也是O(n)：

int fact_r(n)
{
    if(n == 0)
        return 1;
    else
        return n * f(n);
}

但是递归算法要进行n次函数调用，而迭代算法则只需要进行n次迭代而已。其效率上的差异是很显著的。

小结

由以上分析我们可以看到，递归在处理问题时要反复调用函数，这增大了它的空间和时间开销，所以在使用迭代可以很容易解决的问题中，使用递归虽然可以简化思维过程，但效率上并不合算。效率和开销问题是递归最大的缺点。

虽然有这样的缺点，但是递归的力量仍然是巨大而不可忽视的，因为有些问题使用迭代算法是很难甚至无法解决的（比如汉诺塔问题）。这时递归的作用就显示出来了。

递归的效率问题暂时讨论到这里。后面会介绍到递归计算过程与迭代计算过程，讲解得更详细点。

延伸阅读

此文章所在专题列表如下：

1. 漫谈递归：递归的思想
2. 漫谈递归：递归需要满足的两个条件
3. 漫谈递归：字符串回文现象的递归判断
4. 漫谈递归：二分查找算法的递归实现
5. 漫谈递归：递归的效率问题
6. 漫谈递归：递归与循环
7. 漫谈递归：循环与迭代是一回事吗？
8. 递归计算过程与迭代计算过程
9. 漫谈递归：从斐波那契开始了解尾递归
10. 漫谈递归：尾递归与CPS
11. 漫谈递归：补充一些Continuation的知识
12. 漫谈递归：PHP里的尾递归及其优化
13. 漫谈递归：从汇编看尾递归的优化

本文地址：http://www.nowamagic.net/librarys/veda/detail/2321，欢迎访问原出处。