Common Lisp：为什么我的尾递归函数会导致堆栈溢出？ [英] Common Lisp: Why does my tail-recursive function cause a stack overflow?

问题描述

我在理解Common Lisp函数的性能时遇到问题（我仍然是新手）。我有此函数的两个版本，它们仅计算直到给定 n 的所有整数的总和。

I have a problem in understanding the performance of a Common Lisp function (I am still a novice). I have two versions of this function, which simply computes the sum of all integers up to a given n.

非尾递归版本：

(defun addup3 (n) 
  (if (= n 0)
    0   
    (+ n (addup (- n 1)))))

尾递归版本：

(defun addup2 (n) 
  (labels ((f (acc k)
              (if (= k 0)
                   acc 
                   (f (+ acc k) (- k 1)))))
  (f 0 n)))

我试图在CLISP中使用输入 n = 1000000 。结果是

I am trying to run these functions in CLISP with input n = 1000000. Here is the result

[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)

*** - Program stack overflow. RESET

我都可以在SBCL中成功运行，但是非尾递归的速度更快（仅一点点，但这对我来说似乎很奇怪）。我一直在搜寻Stackoverflow问题以寻找答案，但是找不到类似的东西。为什么我设计了尾递归函数而不将所有递归函数调用都放在堆栈上，但为什么会出现堆栈溢出？我是否必须告诉解释器/编译器优化尾部调用？ （我读了类似（proclaim'（optimize（debug 1））之类的东西来设置调试级别并以跟踪能力为代价进行优化，但是我不知道这是什么意思
也许答案是显而易见的，并且代码是胡说八道，但我只是想不通。
表示感谢。

I can run both successfully in SBCL, but the non-tail-recursive one is faster (only by a little, but that seems strange to me). I've scoured Stackoverflow questions for answers but couldn't find something similar. Why do I get a stack overflow although the tail-recursive function is designed NOT to put all recursive function calls on the stack? Do I have to tell the interpreter/compiler to optimise tail calls? (I read something like (proclaim '(optimize (debug 1)) to set the debug level and optimize at the cost of tracing abilities, but I don't know what this does). Maybe the answer is obvious and the code is bullshit, but I just can't figure it out. Help is appreciated.

编辑：danlei指出了错别字，它应该是第一个函数中的 addup3 的调用，因此它是递归的。如果更正，两个版本都会溢出，但不是他的那个

danlei pointed out the typo, it should be a call to addup3 in the first function, so it is recursive. If corrected, both versions overflow, but not his one

(defun addup (n) 
         "Adds up the first N integers"
         (do ((i 0 (+ i 1)) 
              (sum 0 (+ sum i)))
             ((> i n) sum)))

虽然这可能是一种更典型的实现方式，但我发现奇怪的是尾部递归并不总是最优化的，考虑到我的教练想告诉我的更多

While it may be a more typical way to do it, I find it strange that tail recursion is not always optimised, considering my instructors like to tell me it's so much more efficient and stuff.

推荐答案

不需要Common Lisp实现进行尾部呼叫优化。但是，大多数这样做（由于Java虚拟机的限制，我认为ABCL不会这样做）。

There is no requirement for a Common Lisp implementation to have tail call optimization. Most do, however (I think that ABCL does not, due to limitations of the Java virtual machine).

实现文档应告诉您应该使用哪些优化设置选择拥有TCO（如果有）。

The documentation of the implementation should tell you what optimization settings should be chosen to have TCO (if available).

Common Lisp代码使用以下循环结构之一更惯用：

It is more idiomatic for Common Lisp code to use one of the looping constructs:

(loop :for i :upto n
      :sum i)

(let ((sum 0))
  (dotimes (i n)
    (incf sum (1+ i))))

(do ((i 0 (1+ i))
     (sum 0 (+ sum i)))
    ((> i n) sum))

在这种情况下，当然，最好使用小Gauß：

In this case, of course, it is better to use the "little Gauß":

(/ (* n (1+ n)) 2)

这篇关于Common Lisp：为什么我的尾递归函数会导致堆栈溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！