SICP学习笔记之一迭代与递归(1)

SICP学习笔记之一迭代与递归(1)

最近开始学学习《SICP（计算机程序的构造和解释）》，不愧是当年MIT的教材，全本书都是干货，每个章节的每个小节都值得认真推敲，仔细思考，自我感觉收获很大。因此我把自己的学习过程通过系列博客分享给大家，望多多交流。

递归与迭代，是计算机算法的重要组成部分，我们都懂得简单的二叉树遍历与二分查找，但是很少有人深入思考二者之间的异同以及关系。这第一篇博客，就跟大家分享一下自己关于递归与迭代的思考。

1 线性递归与迭代

栗一 阶乘的计算

对于阶乘的计算，相信大家都不陌生，考虑到阶乘的定义：

n! = n*(n-1)*(n-2)*…*2*1

我们可以有很多种方式计算，最简单的就是一个递归算法了，即n！= n*（n-1）！

对应的代码也很简单，我就不多讲了，在此，给出Lisp与Python两种语言的示例：

;用来递归计算阶乘的方法
(define (recursion_fun num)(if (> num 0)(* num (recursion_fun (- num 1)))1))

#用递归计算阶乘的方法
def  factorial_recursion(n):if n == 1:return 1else:return n*factorial_recursion(n-1)

以6！的计算为例，其计算过程展开如图1所示:

图1  计算6！的线性递归过程

注意到上述计算过程的“形状”，因为其过程只有“一条线”，因此被形象地称为线性递归。

其实，对于这种线性递归，我们可以很容易地改为迭代算法。对于阶乘的计算，我们可以换一个角度描述：先将1与2相乘，将得到的结果乘以3，然后再乘以4，这样一直乘到n。而在这个过程中，我们实际上一直在维护着一个中间结果，让它像“滚雪球”一样越乘越大，每一步都只是求一个乘积而已，因此我们完全可以用迭代算法重写我们的程序：

;用迭代计算阶乘的方法
(define (iteration_fun middle_result num maxnum)(if (> num maxnum)middle_result(iteration_fun (* middle_result num)(+ num 1)maxnum)))
;计算阶乘的方法
(define (factorial num)(iteration_fun 1 1 num))

#用迭代计算阶乘的方法
def factorial(n):factorial_iteration(1, 1, n)
def factorial_iteration(middle_result, n, max):if n > max:return middle_resultelse:return n*factorial_iteration(middle_result, n+1, max)

在这里，我们同样以6！的计算为例，分析一下这里的计算过程：

图2  计算6！的迭代过程

对比一下两个过程，二者都需要与n成正比的步骤完成计算，即O（n）的时间复杂度，然而，如果考虑到两者的“形状”，二者情况就大不相同了:

在第一个过程中，显示的是一种先展开后收缩的形状，即函数层层调用但因为无法得到返回值而延迟执行，直到最后一层才得到返回值，进而层层“收缩”的到的最终结果。因此，在过程中我们不得不保存所有的延迟执行的函数 “链条”，直到得到返回值才层层回归释放这长长的链条，“递归”这个词本身就是对这一过程的形象概括。

而在第二个过程中，没有任何的展开与收缩。每步运算中，需要的只是middle_result，num和maxnum这3个变量，只要得到这三个值，函数就能马上得到下一步的结果，不存在延迟执行。可以说，无论计算了几步，3个变量都保存了至今为止所有计算的成果，不需额外保存一条“链条”。

分析到这里，我想大家对于迭代和递归各自的特点已经有一定认识了：首先，由于要在过程中额外保存延迟执行的函数链，递归算法的空间复杂度，即内存占用，通常高于迭代算法，在本例中，递归算法为O（n），迭代算法为O（1）；其次，由于存在延迟执行，递归算法的灵活性显然不如递归算法，比如，在迭代算法中，我们可以在它执行任意步时暂停，并在需要时随时继续我们的运算（只要我们正确保存了3个变量当前的值）。而递归算法则很难完成这一点，因为他的计算过程需要保存的东西太多。

试想一下，如果有一项大型运算任务，可能耗时数日甚至数月，在如此长的时间跨度中，如果出现意外，比如最容易想到也最可怕的停电，对于迭代算法来说，受到的影响可能很小，因为每步运算后只需保存不太多的结果即可保证下一步运算继续，因此只要定时把计算结果保存到硬盘中，就可以保住运算成果，需要时“存档读档”就可以继续运算；而对于递归算法，这种变故就可能是灾难性的: 递归时的“延迟函数链”通常需要存在内存中（备份到硬盘可是很耗资源的，不现实），一旦有一环丢失运算都难以继续了，只能从头再来，而内存掉电不储存的特性恰恰使这种情况极易发生，因此从这个角度看，递归算法本身就是“十分脆弱”的。因此，我们有理由猜测，大型运算中迭代的应用一定比递归普遍。

好了，前面讲了这么多，大家不要误解，我没有丝毫贬低递归的意思，其实，相比于迭代，递归的优势也是很明显的，那就是易于描述和理解，这点对比一下上文中的代码行数就一目了然了。我的理解是，如果把问题比作迷宫，算法用来找到起点到终点的路径，那么递归法倾向于从终点向起点出发解决问题，这样通常只有一条路径到达起点，因此可以更快更容易地解决问题；而迭代算法则更像是从起点出发寻找终点，因此遇到的困难通常会更多些。

为了加深大家对于迭代与递归算法的理解，下面我再举几个栗子，揭示二者更多的特征。

2 树形递归与迭代

上面的阶乘计算的例子中，不论是递归还是迭代，其运算步骤都与n成线性增长，因此被称为线性递归与线性迭代。与之对应的还有树形递归，请看下面的栗子：

栗2  斐波那契(Fibonacci)数列的计算

斐波那契数列，其定义很简单，除前两项外，数列中的每一项都是前两项的和：

0,1,1,2,3,5,8,13,21…

写成函数形式为：

毫无疑问，这个数列用地递归算法的实现是很简单的：

;用递归计算斐波那契数列的方法
(define (fib_recursion n)(if (= n 0)0(if (= n 1)1(+ (fib_recursion (- n 1)) (fib_recursion (- n 2))))))

#递归法计算斐波那契数列的方法
def fib_recursion(n):if n == 0:return 0elif n == 1:return 1elif n > 1:return fib_recursion(n-1)+fib_recursion(n-2)

图3是以fib（5）的计算为例给出的算法计算过程：

 

 图3 计算fib 5产生的树形递归过程

考虑这一过程，为了计算fib(5)，我们需要计算fib(4)与fib(3)，为了计算fib(4)，又要计算fib(3)和fib(2)，按照此规则，我们会发现其过程展开像一棵树，如图3所示，其中每层分裂为两个分支（除了最下面），反映了函数每层两次调用自身。

上面的过程，作为典型树形递归具有教育意义，但是作为计算斐波那契数列的方法，它做了太多的冗余计算——在这里，计算了2次fib(3),3次fib(2)，5次fib(1)…想象一下，如果现在我们要计算fib 6，那么我们不光要再计算一遍fib(5)，还得计算一遍fib(4)，而后者显然相当于前者工作量的一半以上，也就是说，计算fib(6)的工作量至少是fib(5) 的1.5倍以上，这个算法的计算步数是随着n成指数增长的！

事实上，fib(n)是最接近 <!--[endif]-->的整数（证明见附录），也就是说仅计算fib(100)所需要的计算次数就是6x10^20次，按照家用计算机200亿次/秒的运算速度（非官方数据），需要计算900多年，即使是我们全人类最快的“天河二号”超级计算机，也至少需要计算3小时才能完成。很显然，这个算法效率低的令人发指！

我们也可以提出一种计算斐波那契数列的的迭代过程，其基本思路就是将a和b赋予初值fib(1) = 1和fib(0) = 0，然后不断使用下面的变换规则：

这样，在应用n次这样的变换后，a和b将分别等于fib(n+1)和fib(n)。同样的，我们不难把它翻译成代码：

;用迭代计算斐波那契数列的方法
(define (fib n)(fib_iteration 1 0 n))(define (fib_iteration a b count)(if (= count 0)b(fib_iteration (+ a b)a(- count 1))))

#迭代法计算斐波那契数列的方法
def fib(n):return fib_iteration(1,0,n)
def fib_iteration(a,b,n):if n == 0:return belse:return fib_iteration(a+b,a,n-1)

显然，此迭代算法计算抓住了斐波那契数列运算的本质，即fib(n+1)和fib(n)两个变量的“滚雪球”式变换，因此在中间结果中不光保存fib(n)，还保存了fib(n+1)的值，从而避免了树形递归中出现的大量冗余计算，提高了效率。不难证明，迭代计算fib(100)只要100次加法即可，这是我们用铅笔就可以完成的任务；同时，整个过程也只需要3个变量的内存，不需要保存庞大的递归树。

       在本栗中，递归算法似乎又是完败，不过我们也不要小视递归算法这个“安静的美男子”，很多情况下，递归算法仍是给力的工具。下一篇博客，笔者就会举几个用递归方法容易解决而难以用迭代算法解决的栗子，展示递归算法的强大。大家拭目以待吧！