Common Lisp:为什么我的尾递归函数导致堆栈溢出？

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)))

我试图在输入CLISP中运行这些函数n = 1000000.这是结果

[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))

在这种情况下,当然,最好使用"小高斯":

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

Answer 2

好吧,你的addup3公正根本不是递归的.

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

它称之为addup.在SBCL中尝试更正版本:

CL-USER> (defun addup3 (n) 
           (if (= n 0)
               0   
               (+ n (addup3 (- n 1)))))
ADDUP3
CL-USER> (addup3 100000)
Control stack guard page temporarily disabled: proceed with caution
;  ..
; Evaluation aborted on #<SB-SYS:MEMORY-FAULT-ERROR {C2F19B1}>.

正如你所料.