common-lisp - 常见的Lisp : Why does my tail-recursive function cause a stack overflow?

Question

我在理解Common Lisp函数的性能时遇到了问题(我仍然是新手)。我有此函数的两个版本，它们仅计算直到给定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)))

我正在尝试使用输入n = 1000000在CLISP中运行这些功能。这是结果

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

*** - Program stack overflow. RESET

我可以在SBCL中成功运行两者，但是非尾递归的速度更快(只有一点点，但这对我来说很奇怪)。我一直在寻找Stackoverflow问题的答案，但找不到类似的东西。为什么我设计了尾递归函数而不将所有递归函数调用都放在堆栈上，为什么会出现堆栈溢出？我是否必须告诉解释器/编译器优化尾部调用？ (我读了(proclaim '(optimize (debug 1))之类的东西来设置调试级别并以跟踪能力为代价进行优化，但是我不知道这是怎么做的)。
也许答案很明显，并且代码很胡扯，但是我无法弄清楚。
感谢您的帮助。

编辑:danlei指出了拼写错误，它应该是第一个函数中对addup3的调用，因此它是递归的。如果更正，则两个版本都会溢出，但不会溢出

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

尽管这可能是一种更典型的方法，但我发现奇怪的是尾部递归并不总是最佳的，考虑到我的教练想告诉我它的效率和效率要高得多。

Answer 1

不需要Common Lisp实现具有尾部调用优化。但是，大多数这样做(由于Java虚拟机的限制，我认为ABCL不会这样做)。

实现文档应告诉您应该选择哪些优化设置以拥有TCO(如果有)。

对于Common Lisp代码，使用以下循环结构之一更为习惯:

(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ß”:

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