SICP笔记 - 递归与迭代

Aug 20, 2018

sicp-cover

这篇文章会很简短,因为我只准备谈一个简单的问题,就是递归与迭代之间的转换技巧。在我看了80页SICP之后,我觉得我有必要记下这个技巧,很难想象我从前从来没有总结过这个技巧,只是模糊地思考。

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

拿最简单的阶乘(Factorial)来说好了,当我们使用一段递归程序来计算6的阶乘的时候(譬如上面这段Lisp程序),稍微有点基础的人都知道,程序内部的堆栈是这样的:

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

现在请思考,如果要实现递归,我们最需要的计算机特性是什么?

我觉得应该是计算机可以保存现场与恢复现场的能力。打个比方,层层递归就好像往一条小路上走,一直走到尽头,但是在走的过程中,你必须记下路上的标记,因为你最终需要回到你走的起点。在这个例子中,程序想要知道(* 6 (factorial 5))的值,它就必须知道(factorial 5)的值,但是同时,它也必须记住6这个值,因为后续我们还会用到,只是现在它用不到罢了。

这样思考之后,递归的本质就明显了,我认为递归的本质就是迭代,不同之处在于,递归利用程序内部的堆栈来存储中间变量,而迭代使用参数来存储中间变量。如果想要将一段递归程序转换为一段迭代程序,只需增加几个参数即可,参数的个数取决于这段程序需要的中间变量的个数。

如此一来,计算阶乘的递归程序可以改写为以下的迭代程序:

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
  (fact-iter 1 1 n))

除了递归程序中原有的参数n以外,这里又加上了productcounter参数,发现了吗?其实productcounter两个参数所扮演的角色就是堆栈在递归程序中所扮演的角色。所以递归程序如何变成迭代程序呢?加参数就可以了。

递归与迭代,一个用堆栈记录信息,一个用参数记录信息,仅此而已。

(The End)

[Return to the homepage]