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

Question

我正在从Conrad Barski的书《Lisp之国》中学习Lisp。现在我遇到了第一个难题，作者说：

在Lisp中，这种自我调用不仅是被允许的，而且经常会受到强烈的鼓励。

在展示了以下计算列表项数目的示例函数后：

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

当我使用包含一百万项的列表调用这个函数my-length时，会出现堆栈溢出错误。所以，要么你从不指望在Lisp中有那么长的列表（所以也许我的用例是无用的），要么就有另一种方法来计算这么长的列表中的项目数。你能否为此提供一些帮助？（顺便说一下，我在Windows上使用GNU CLISP）。

- mydoghasworms

---

http://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html - David Brabant

你知道在Lisp中有一个length函数，对吧？所以你才叫你自己的函数为my-length。因此，你要么从未预料到会有这么长的列表，要么就是故意不使用基础函数。 - Kaz

Answer 1

使用Chris Taylor的例子，在CLISP中进行尾调用优化（TCO）：

[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编译器执行尾递归优化通常由调试级别控制。在高调试级别下，编译器生成的代码对于每个函数调用都使用一个堆栈帧。这样每个调用都可以被跟踪并在回溯中看到。在较低的调试级别下，编译器可能会在编译代码中用跳转替换尾调用。这些调用将不会在回溯中看到 - 这通常使调试更加困难。

- Rainer Joswig

---

我只是想知道为什么这个答案没有被接受为正确答案。非常有用的信息，谢谢。 - Pankaj Sejwal

借助这个工具，我计算出了10万的阶乘。 - Pankaj Sejwal

Answer 2

您正在寻找尾递归。目前您的函数定义如下：

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

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

您可以重写它以使用辅助函数。

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

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

这个辅助函数接受两个参数，一个是累加器 acc，用于存储到目前为止列表的长度，另一个是列表 list，我们要计算其长度。

重要的一点是，helper 是尾递归写法，这意味着调用自身是它所做的最后一件事情。这意味着每次函数调用自身时都不需要分配新的栈帧 - 由于最终结果将被传递回整个栈帧链，因此可以通过用新的栈帧覆盖旧的栈帧来避免分配过多的内存，从而使得递归函数可以在常量空间内操作。

将一个递归（但非尾递归）定义转换为等效的使用尾递归辅助函数的定义的这种程序转换形式，是函数式编程中的一种重要习语 - 值得花些时间去理解。

- Chris Taylor

---

谢谢，你展示了Rolf在他的答案中提到的内容，但即使使用这段代码（在GNU Clisp上），我仍然遇到堆栈溢出的问题。 - mydoghasworms

有趣。你有另一个通用Lisp实现可以尝试吗？这个关于Common Lisp实现中尾调用优化的页面没有明确说明GNU Clisp是否执行尾调用优化。 - Chris Taylor

可能有一种优化级别可以在CLISP中启用尾递归优化，但是谷歌没有返回任何权威文档说明这在CLISP中如何工作。 - Rolf Rander

谢谢您提供这个漂亮而简单的尾调用优化示例。我听到过这个术语被频繁使用，但直到现在才开始了解它。这个示例非常简单明了，我认为它应该出现在维基百科关于尾调用优化的页面上。 - Faheem Mitha

Answer 3

创建递归函数以操作递归数据结构在Lisp中确实是好的。而列表（在Lisp中）被定义为递归数据结构，因此您应该没问题。但是，正如您所经历的那样，如果使用递归遍历具有百万项深度的数据结构，也会在堆栈上分配一百万个帧，除非您明确要求运行时环境分配大量堆栈空间（我不知道您是否可以在GNU CLISP中这样做...）。首先，我认为这表明列表数据结构并不是万能的，在这种情况下，另一个结构可能更好（但是，您可能还没有在Lisp书中看到向量;-)）。另一件事是，为了使这样的大型递归有效，编译器应优化尾递归并将其转换为迭代。我不知道clisp是否具有此功能，但您需要更改函数以使其实际可优化。（如果“尾递归优化”没有意义，请告诉我，我可以找一些参考资料）。对于其他迭代方式，请参阅：

• 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/t_vector.htm

- Rolf Rander

---

很酷，非常感谢。对我来说要记住的是：1）列表并不是万能的，2）还有其他数据结构可以考虑。我很想学习更多关于尾递归优化的知识，但也许在我掌握基础之后再学习吧;-) 谢谢！ - mydoghasworms

Answer 4

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

- Cristian Tugui