这篇文章会很简短，因为我只准备谈一个简单的问题，就是递归与迭代之间的转换技巧。在我看了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以外，这里又加上了product与counter参数，发现了吗？其实product与counter两个参数所扮演的角色就是堆栈在递归程序中所扮演的角色。所以递归程序如何变成迭代程序呢？加参数就可以了。

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

(The End)