0 写在前面

递归就是将一个问题以“减而治之”的思想分解为一个平凡数和另外一个规模缩小的子问题，另外一个子问题也可以用相似想法继续分解下去。或者说，递归就是将一个问题以“分而治之”的思想分解为一个规模缩小的子问题和另外一个规模缩小的子问题，两个规模缩小的子问题也可以用相似想法继续分解下去。

递归是好东西，但是对于大规模问题，递归的设计非常重要，不然就会造成巨大问题。可以使用递归跟踪（recursion trace）或者递归方程去分析递归算法的效率。

如果一个问题可以递归解决、也可以用迭代解决，鉴于递归这么烦人的特性（难设计好），优先用迭代解决问题。

1 为什么推荐迭代法解决问题？

参考邓军辉老师的数据结构与算法C++版本的书籍。

以前上课，老师很推荐递归，以前有句话叫“迭代乃人工，递归方神通”，因为递归出来的一切都是程序自己调用自己负责的，突显了程序的智能特性。但可能现在我们得推荐由递归转向迭代 。

递归也是一种基本而典型的算法设计模式。这一模式可以对实际问题中反复出现的结构和形

式做高度概括，并从本质层面加以描述与刻画，进而导出高效的算法。从程序结构的角度看，递

归模式能够统筹纷繁多变的具体情况，避免复杂的分支以及嵌套的循环，从而更为简明地描述和

实现算法，减少代码量，提高算法的可读性，保证算法的整体效率。

递归很容易造成空间浪费和效率不行，学习了数据结构与算法这门课，就得学会去分析问题：一般地，能用迭代方法解决问题的，就尽量想出一个迭代的方法，而不要使用递归，因为递归太难设计妥当。

从递归跟踪分析的角度不难看出，递归算法所消耗的空间量主要取决于递归深度（习

题[1-17]），故较之同一算法的迭代版，递归版往往需耗费更多空间，并进而影响实际的运行

速度。另外，就操作系统而言，为实现递归调用需要花费大量额外的时间以创建、维护和销毁各

递归实例，这些也会令计算的负担雪上加霜。有鉴于此，在对运行速度要求极高、存储空间需精

打细算的场合，往往应将递归算法改写成等价的非递归版本。

2 什么是递归？

斐波那契数列的通项公式是：

在这里插入图片描述

下面就是一个设计得很糟糕的递归算法：

c
__int64 fib(int n)
{
    return (2 > n) ? (__int64)n : fib(n - 1) + fib(n - 2);
}

如果调用fib(10)，程序会计算fib(9)和fib(8)，然后计算fib(8)和fib(7)、fib(7)和fib(6)……

可见程序会重复计算一些之前已经计算过的数值，当问题规模变大时，比如求fib(100)，运行O(2^n)时间时间才能计算完毕，而且巨大地浪费内存，这违背高效率准则。

3 递归的形式

递归在有的情况里，还是非常经典的。并不是递归不好，而是递归的设计更难（如果你想要高效率）。

递归的形式有：线性递归、二分递归和多分支递归等

3.1 线性递归求数组的前n项和

c
//线性递归
int sum(int A[], int n)
{
    if (1 > n)
        return 0;
    else
        return sum(A, n - 1) + A[n - 1];
}

线性递归的模式，往往对应于所谓减而治之（decrease-and-conquer）的算法策略：递归

每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。

按照减而治之策略，此处随着递归的深入，调用参数将单调地线性递减。因此无论最初输入

的n有多大，递归调用的总次数都是有限的，故算法的执行迟早会终止，即满足有穷性。当抵达递归基时，算法将执行非递归的计算（这里是返回0）。

3.2 二分递归求数组的前n项和

往往对应于所谓分而治之的算法策略

c
int sum(int A[], int lo, int hi)
{
    if (lo == hi)
        return A[lo];
    else
    {
        int mi = (lo + hi) >> 1;
        return sum(A, lo, mi) + sum(A, mi + 1, hi);
    }
}

3.3 如何正确线性递归斐波那契数列

为使分治策略真正有效，不仅必须保证以上两方面的计算都能高效地实现，还必须保证子问

题之间相互独立各子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。否则，

或者子问题之间必须传递数据，或者子问题之间需要相互调用，无论如何都会导致时间和空间复杂度的无谓增加。

之间那个设计得不好的递归就是没有考虑好上面所说的问题。

  优化策略为消除递归算法中重复的递归实例，一种自然而然的思路和技巧，可以概括为：借助一定量的辅助空间，

在各子问题求解之后，及时记录下其对应的解答比如，可以从原问题出发自顶而下，每当遇到一个子问题，都首先查验它是否已经计算过，

以期通过直接调阅记录获得解答，从而避免重新计算。也可以从递归基出发，自底而上递推地得

出各子问题的解，直至最终原问题的解。前者即所谓的制表（tabulation）或记忆（memoization）

策略，后者即所谓的动态规划（dynamic programming）策略。

线性递归版fib()算法，消耗线性时间，但是耗费了O(n)的空间量。

c
__int64 fib(int n, __int64& prev)
{ 
    if (0 == n) 
    {
        prev = 1;
        return 0;
    } 
    else
    { 
        __int64 prevPrev;
        prev = fib(n - 1, prevPrev); 
        return prevPrev + prev; 
    }
}

4 什么是迭代？

迭代是什么？从名词上就可以分析出来，迭代迭代，计算了这一轮的结果，然后把结果带入了下一轮的计算中！这一轮的输出是下一轮的输入，我们只需要给出迭代轮数（满足某个条件），迭代就可以继续。

迭代方式解决斐波那契数列

c
__int64 fibI(int n)
{
    __int64 f = 0, g = 1;
    while (0 < n--)
    {
        g += f;
        f = g - f;
    }
    return f;
}

5 总结

现在就该知道迭代和递归是什么了。

无论设计递归算法还是设计迭代算法：递归到最终肯定有一个基解，从而能够终止递归；迭代肯定也需要有终止条件，不然就会无止境运算。

目录