gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 12:30:23 25 4
gpt4 key购买 nike

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

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

最佳答案

不需要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)

关于common-lisp - 常见的Lisp : Why does my tail-recursive function cause a stack overflow?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16626736/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com