Lisp中递归函数调用引起的堆栈溢出 [英] Stack overflow from recursive function call in Lisp
问题描述
我正在从康拉德·巴尔斯基(Conrad Barski)的书《 Lisp的土地》中学习Lisp.现在我打了我的第一个绊脚石，作者说:
I am learning Lisp from the book "The Land of Lisp" by Conrad Barski. Now I have hit my first stumbling block, where the author says:
不仅在Lisp中允许以这种方式打电话给自己，而且经常 强烈鼓励
Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged
在显示以下示例函数以对列表中的项目进行计数之后:
after showing the following example function to count the items in a list:
(defun my-length (list)
(if list
(1+ (my-length (cdr list)))
0))
当我使用包含一百万个项目的列表调用此函数my-length时，出现堆栈溢出错误.因此，或者您永远都不会期望在Lisp中拥有如此长的列表(因此，也许我的用例是没有用的)，或者还有另一种方法来计算如此长的列表中的项目.您能否对此有所启发? (顺便说一下，我正在Windows上使用GNU CLISP.)
When I call this function my-length with a list containing a million items, I get a stack overflow error. So either you never expect to have a list that long in Lisp (so maybe my use case is useless) or there is another way to count items in such a long list. Can you maybe shine some light on this? (I am using GNU CLISP on Windows, by the way).
推荐答案
创建递归函数以对递归数据结构进行操作确实对lisp有好处.并且列表(以Lisp格式)被定义为递归数据结构，因此您应该没事.
Creating recursive functions to operate on recursive datastructures is indeed good for in lisp. And a list (in lisp) is defined as a recursive datastructure, so you should be ok.
但是，正如您所经历的那样，如果使用递归遍历一百万个数据项的深度，也会在堆栈上分配一百万个帧，并且除非您特别要求运行时环境分配大量的数据，否则可能会出现堆栈溢出堆栈空间(我不知道您是否或如何在gnu clisp中执行此操作...).
However, as you have experienced, if traversing a datastructure a million items deep using recursion, will also allocate a million frames on the stack, and you can expect a stack overflow unless you specifically ask your runtime environment to allocate huge amount of stack-space (I have no idea if or how you could do this in gnu clisp...).
首先，我认为这表明列表数据结构并不是所有功能的最佳选择，在这种情况下，另一种结构可能会更好(但是，您可能没有在Lisp书中找到矢量还;-)
First of all, I think this shows that the list-datastructure isn't really a the best for everything, and in this case another structure might be better (however, you might not have come to vectors in your lisp-book yet ;-)
另一件事是，要使大型递归有效，编译器应优化尾递归并将其转换为迭代.我不知道clisp是否具有此功能，但是您需要将功能更改为实际上是可优化的. (如果尾递归优化"没有意义，请让我知道，我可以找出一些参考文献)
Another thing is that for large recursions such as this to be effective, the compiler should optimise tail recursions and convert them into iterations. I don't know if clisp has this functionality, but you would need to change your function to actually be optimisable. (If "tail recursion optimisation" makes no sense, please let me know and I can dig up some references)
有关其他迭代方式，请查看:
For other ways of iterating, take a look at:
- http://www.lispworks.com/documentation/HyperSpec/Body /c_iterat.htm
- http://www.lispworks.com/documentation/HyperSpec/Body /06_a.htm
- http://www.lispworks.com/documentation/HyperSpec/Body/c_iterat.htm
- http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm
或其他数据结构:
这篇关于Lisp中递归函数调用引起的堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
