SICP笔记 - 递归与迭代
source link: http://idle.systems/posts/sicp-recursion-iteration.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
SICP笔记 - 递归与迭代
Aug 20, 2018
这篇文章会很简短，因为我只准备谈一个简单的问题，就是递归与迭代之间的转换技巧。在我看了80页SICP之后，我觉得我有必要记下这个技巧，很难想象我从前从来没有总结过这个技巧，只是模糊地思考。
拿最简单的阶乘（Factorial）来说好了，当我们使用一段递归程序来计算6的阶乘的时候（譬如上面这段Lisp程序），稍微有点基础的人都知道，程序内部的堆栈是这样的：
现在请思考，如果要实现递归，我们最需要的计算机特性是什么？
我觉得应该是计算机可以保存现场与恢复现场的能力。打个比方，层层递归就好像往一条小路上走，一直走到尽头，但是在走的过程中，你必须记下路上的标记，因为你最终需要回到你走的起点。在这个例子中，程序想要知道(* 6 (factorial 5))的值，它就必须知道(factorial 5)的值，但是同时，它也必须记住6这个值，因为后续我们还会用到，只是现在它用不到罢了。
这样思考之后，递归的本质就明显了，我认为递归的本质就是迭代，不同之处在于，递归利用程序内部的堆栈来存储中间变量，而迭代使用参数来存储中间变量。如果想要将一段递归程序转换为一段迭代程序，只需增加几个参数即可，参数的个数取决于这段程序需要的中间变量的个数。
如此一来，计算阶乘的递归程序可以改写为以下的迭代程序：
除了递归程序中原有的参数n以外，这里又加上了product与counter参数，发现了吗？其实product与counter两个参数所扮演的角色就是堆栈在递归程序中所扮演的角色。所以递归程序如何变成迭代程序呢？加参数就可以了。
递归与迭代，一个用堆栈记录信息，一个用参数记录信息，仅此而已。
(The End)
This page has been viewed for 231 times
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK