5

我认识到输出中有一个明显的模式，我只是想知道为什么当我尝试运行任何 > 52 的东西时 lispbox 的 REPL 会中止。此外，任何关于改进代码的建议都非常受欢迎。^-^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

我打电话时得到的一切

(count-reduced-fractions 53 53 0)

是

;评估中止

这对我来说没有多大意义，考虑到它会在低于此的所有数字上运行（并返回准确的结果），而且我可以（如果我愿意）在我的头脑中、纸上或一行上做 53一次在 lisp 中。我什至测试了许多大于 53 的不同数字，以确保它不是特定于 53。没有任何效果。

4

4 回答 4

6

此行为暗示缺少尾调用优化，因此您的递归会破坏堆栈。一个可能的原因是您声明了调试优化。

顺便说一句，您不需要显式调用return-from. 由于sum是自评估符号，您可以更改此行

(return-from count-reduced-fractions sum)

至

sum

编辑：建议更改的解释：“sum”评估为它自己的值，它成为“if”语句的返回值，它（因为这是 defun 中的最后一条语句）成为函数的返回值。

编辑：声明的优化说明：您可以将以下内容添加到顶层：

(declaim (optimize (speed 3)
                   (debug 0)))

或使用相同的，但使用declare而不是declaim作为函数中的第一条语句。如果不起作用，您也可以尝试 (space 3) 和 (safety 0)。

尾调用优化是指将直接返回返回值的函数调用翻译成栈上的帧替换（而不是堆叠起来），有效地将递归函数调用“扁平化”为循环，消除递归函数调用。这使调试变得更加困难，因为在您期望它们的地方没有函数调用。您不知道错误发生在递归中的“深度”程度（就像您从一开始就编写了一个循环一样）。您的环境可能会做出一些您必须覆盖以启用 TCO 的默认声明。

编辑：只是重新审视这个问题，什么是g？我认为你实际上想要

(let ((g (gcd n d)))
  ;; ...
  )
于 2008-12-10T00:21:53.403 回答
3

我的猜测是 lispbox 有一个内置的堆栈深度限制。由于 Common Lisp 不保证尾递归函数使用常量堆栈空间，因此每次调用 count-reduced-fractions 都可能在堆栈上添加另一层。

顺便说一句，SBCL 运行这个算法没有问题。

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043
于 2008-12-10T00:11:24.157 回答
1

作为风格问题，您可以将 d 和 sum 设为可选。

(defun test (n &optional (d n) (sum 0)) .. )
于 2008-12-10T00:15:44.773 回答
0

可能是堆栈溢出（呵呵）。

于 2008-12-10T00:10:53.050 回答