lisp - 与欧拉项目 72 (lisp) 有关的奇怪问题

Question

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

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

是

;Evaluation aborted

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

Answer 1

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

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

(return-from count-reduced-fractions sum)

到

sum

编辑: 提议更改的解释:“sum”计算为它自己的值，成为“if”语句的返回值，这(因为这是 defun 中的最后一个语句) 成为函数的返回值。

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

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

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

尾调用优化是指将直接返回返回值的函数调用翻译成栈上的帧替换(而不是上栈)，有效地将递归函数调用“扁平化”为一个循环，消除递归函数电话。这使得调试变得有点困难，因为在你期望的地方没有函数调用，resp。你不知道错误发生在递归中有多“深”(就像你一开始就写了一个循环一样)。您的环境可能会做出一些默认声明，您必须覆盖这些声明才能启用 TCO。

编辑: 重新审视这个问题，g 是什么？我认为你真的想要

(let ((g (gcd n d)))
  ;; ...
  )