8

我在理解 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)))

虽然这可能是一种更典型的方式，但我觉得奇怪的是尾递归并不总是优化的，考虑到我的导师喜欢告诉我它效率更高等等。

4

4 回答 4

9

Common Lisp 实现不需要进行尾调用优化。但是，大多数都可以（我认为 ABCL 不会，因为 Java 虚拟机的限制）。

实施文档应该告诉您应该选择哪些优化设置来获得 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)
于 2013-05-18T20:50:06.853 回答
6

好吧，您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}>.

如你所料。

于 2013-05-19T05:34:14.217 回答
1

使用 GNU CommonLisp，GCL 2.6.12，编译addup2将优化尾调用，这是我得到的：

>(compile 'addup2)                                                                     

Compiling /tmp/gazonk_3012_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of F was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /tmp/gazonk_3012_0.lsp.
Loading /tmp/gazonk_3012_0.o
start address -T 0x9556e8 Finished loading /tmp/gazonk_3012_0.o
#<compiled-function ADDUP2>
NIL
NIL

>>(addup2 1000000)                                                                                                                                            

500000500000
>(addup3 1000000)

Error: ERROR "Invocation history stack overflow."
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by IF.
ERROR "Invocation history stack overflow."

Broken at +.  Type :H for Help.
    1  Return to top level. 

>>(compile 'addup3)                                                                                                                                           

Compiling /tmp/gazonk_3012_0.lsp.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /tmp/gazonk_3012_0.lsp.
Loading /tmp/gazonk_3012_0.o
start address -T 0x955a00 Finished loading /tmp/gazonk_3012_0.o
#<compiled-function ADDUP3>
NIL
NIL
>>(addup3 1000000)                                                                                                                                            

Error: ERROR "Value stack overflow."

希望能帮助到你。

于 2016-07-04T07:31:56.357 回答
0

在 SBCL用户手册中：

编译器是“适当的尾递归”。[...] 可以通过禁用尾递归优化来防止尾递归帧的消除，当调试优化质量大于 2 时会发生这种情况。

并在新图像的 REPL 中工作：

(defun sum-no-tail (n)
  (if (zerop n)
      0
      (+ n (sum-no-tail (- n 1)))))

(defun sum-tail (n &key (acc 0))
  (if (zerop n)
      acc
      (sum-tail (- n 1) :acc (+ n acc))))

CL-USER> (sum-no-tail 10000)
50005000 (26 bits, #x2FB0408)
CL-USER> (sum-no-tail 100000)
Control stack guard page temporarily disabled: proceed with caution
; Debugger entered on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
[1] CL-USER> 
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
CL-USER> (sum-tail 100000)
5000050000 (33 bits, #x12A06B550)
CL-USER> (sum-tail 1000000)
500000500000 (39 bits, #x746A5A2920)
CL-USER> (sum-tail 10000000)
50000005000000 (46 bits, #x2D7988896B40)

希望它对 SBCL 有所帮助。

于 2021-09-16T15:58:27.723 回答