关于项目euler 72(lisp)的奇怪问题

Question

我认识到输出中有一个明显的模式,我只是想知道为什么当我尝试运行任何> 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在口齿不清的时候.我甚至测试了大于53的许多不同的数字,以确保它不是特定于53.没有任何作用.

Answer 1

此行为暗示缺少尾调用优化,以便您的递归打击堆栈.可能的原因是您已声明调试优化.

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

(return-from count-reduced-fractions sum)

至

sum

edit:建议更改的解释:"sum"计算其自己的值,该值成为"if"语句的返回值,该值(因为这是defun中的最后一个语句)成为函数的返回值.

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

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

或者使用相同的,而declare不是declaim作为函数中的第一个语句.如果它不起作用,你也可以尝试(空间3)和(安全0).

尾调用优化意味着直接返回其返回值的函数调用被转换为堆栈上的帧替换(而不是堆叠),有效地"展平"对循环的递归函数调用,并消除递归函数调用.这使得调试变得更加困难,因为没有函数调用可以在你期望的地方调用.你不知道如何"深入"一个递归错误发生(就像你已经编写了一个循环开始).您的环境可能会生成一些必须覆盖的默认声明以启用TCO.

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

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

Answer 2

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