Lisp中递归函数调用的堆栈溢出

我正在从Conrad Barski的书“Lisp的土地”学习Lisp。现在，我已经打了我的第一个拦路虎，在这里笔者说：Lisp中递归函数调用的堆栈溢出

以这种方式调用自己是不是只允许在Lisp的，但往往是显示下面的例子功能后，大力鼓励

算在列表中的项目：

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0))

当我调用该函数my-length含一百万的项目清单，我得到一个堆栈溢出错误。所以要么你永远不会期望在Lisp中有很长的列表（所以也许我的用例是无用的），或者有另一种方法来计算这样一个长列表中的项目。你能否对此有所了解？（顺便说一句，我在Windows上使用GNU CLISP）。

来源

2013-03-07 mydoghasworms

http://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html – 2013-03-07 11:03:40

> *所以，要么你就休想有一个长的Lisp *你知道，有一个'length'功能列表，对？这就是为什么你叫你'我的长度'。 – Kaz 2017-05-24 19:24:24

创建递归函数以在递归数据结构上操作确实对lisp很有用。列表（在lisp中）被定义为递归数据结构，所以你应该没问题。然而，正如你所经历的那样，如果使用递归遍历一百万个数据结构，那么它也会在堆栈中分配一百万帧，除非特别要求运行时环境分配巨额金额，否则可能会出现堆栈溢出的堆栈空间（我不知道你是否可以在gnu clisp中做到这一点...）。首先，我认为这表明列表数据结构并非真正适合所有事情，在这种情况下，其他结构可能会更好（但是，您可能没有在您的lisp中找到向量） book yet ;-)

另一件事是，对于像这样的大型递归是有效的，编译器应该优化尾递归并将它们转换为迭代。我不知道clisp是否具有此功能，但您需要将您的功能更改为实际可优化的功能。（如果“尾递归优化”是没有意义的，请让我知道，我可以挖掘出一些参考）

对于迭代的其他方式，一起来看看：

或者其他数据结构：

http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm

来源

2013-03-07 10:58:14

很酷，非常感谢。拿走我：1）列表并不是最好的，2）有其他数据结构可供查看。我很想了解更多关于尾递归优化的知识，但也许在稍后的阶段，我已经征服了基础知识;-)谢谢！ – mydoghasworms 2013-03-07 11:15:52

您正在寻找尾递归。目前你的函数定义像

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0))

注意后my-length呼吁本身，它需要一个值传递给它的调用函数之前添加一个结果。这需要在返回之前修改该值，这意味着您需要为每个调用分配一个新的堆栈帧，所使用的空间与列表的长度成正比。这是导致长列表上堆栈溢出的原因。

您可以重新写它使用一个辅助功能

(defun helper (acc list) 
    (if list 
    (helper (1+ acc) (cdr list)) 
    acc)) 

(defun my-length (list) 
    (helper 0 list))

的辅助函数有两个参数，一个积累参数acc，其中存储列表的长度，到目前为止，名单list这是我们计算长度的列表。

重要的一点是，helper是递归地写尾，这意味着调用自己是它最后一件事。这意味着每次函数自己调用时都不需要分配一个新的堆栈框架 - 因为最终的结果将一直通过堆栈框架的链路，您可以避免覆盖旧的堆栈框架一个新的，所以你的递归函数可以在恒定的空间中运行。

这种形式的程序转换 - 从递归（但非尾递归）定义到使用尾递归辅助函数的等价定义是函数式编程中一个重要的习惯用法 - 值得花一点时间理解。

来源

2013-03-07 11:05:11

谢谢，你已经展示了Rolf在他的回答中暗示的内容，但即使使用这个代码（在GNU Clisp上），我仍然会遇到堆栈溢出。 – mydoghasworms 2013-03-07 11:17:11

有趣。你有没有另一种常见的lisp实现，你可以试试它？对于是否在GNU Clisp中执行尾部呼叫优化，这个[关于通用lisp实现中尾部呼叫优化的页面]（http://0branch.com/notes/tco-cl.html）并不清楚。 – 2013-03-07 11:29:57

我刚刚在钢铁银行Common Lisp上试过，而且工作。 – mydoghasworms 2013-03-07 11:34:26

使用TCO克里斯·泰勒的例子（尾调用优化）在CLISP：

[1]> (defun helper (acc list) 
     (if list 
      (helper (1+ acc) (cdr list)) 
      acc)) 

(defun my-length (list) 
    (helper 0 list)) 

HELPER

现在编译：

[2]> (compile 'helper) 
MY-LENGTH 
[3]> (my-length (loop repeat 100000 collect t)) 

*** - Program stack overflow. RESET

现在，上述方法无效。让我们设置低调试级别。这允许编译器执行TCO。

[4]> (proclaim '(optimize (debug 1))) 
NIL

再次编译。

[5]> (compile 'helper) 
HELPER ; 
NIL ; 
NIL 
[6]> (my-length (loop repeat 100000 collect t)) 
100000 
[7]>

工程。

允许Common Lisp编译器执行TCO通常由调试级别控制。在高调试级别下，编译器会为每个函数调用生成使用堆栈帧的代码。通过这种方式，每个呼叫都可以被追踪，并且会在回溯中看到。如果调试级别较低，编译器可能会用编译代码中的跳转替换尾调用。这些调用然后不会在回溯中看到 - 这通常会使调试更困难。

来源

2013-03-07 12:54:45

我只是想知道为什么这不被接受为正确的答案。非常棒的信息，谢谢。 – Rorschach 2014-03-25 11:44:00

在此帮助下，我计算了100,000的阶乘。 – Rorschach 2014-03-25 11:54:38

(DEFUN nrelem(l) 
    (if (null l) 
     0 
     (+ (nrelem (rest l)) 1) 
))

来源

2015-03-29 17:04:56 IoanCristian

Lisp中递归函数调用的堆栈溢出

回答

相关问题