Странный вопрос, касающийся проекта euler 72 (lisp)

Question

Я признаю, что в выводе есть очевидная закономерность, я просто хочу знать, почему REPL в lispbox прерывается, когда я пытаюсь запустить что-либо> 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)

есть

; Оценка прервана

Это не имеет особого смысла для меня, учитывая, что он будет работать (и даст точный результат) на всех числах ниже этого, и что я мог бы (если бы захотел) сделать 53 в своей голове, на бумаге, или по одной строчке за раз в лисп. Я даже проверил на разных числах больше 53, чтобы убедиться, что он не относится к 53. Ничего не работает.

Answer 1

Это поведение намекает на отсутствующую оптимизацию хвостового вызова, так что ваша рекурсия разрушает стек. Возможная причина в том, что вы объявили оптимизацию отладки.

Кстати, вам не нужно делать явный вызов return-from. Поскольку sum является самооценочным символом, вы можете изменить эту строку

(return-from count-reduced-fractions sum)

до

sum

edit: Объяснение предлагаемого изменения: «sum» возвращает свое собственное значение, которое становится возвращаемым значением оператора «if», который (так как это последний оператор в defun) становится возвращаемым значением функции.

edit: Объяснение объявленной оптимизации: Вы можете добавить следующее к своему верхнему уровню:

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

или используйте то же самое, но с declare вместо declaim в качестве первого оператора в вашей функции. Вы также можете попробовать (пробел 3) и (безопасность 0), если это не сработает.

Оптимизация вызова Tail означает, что вызов функции, возвращаемое значение которой напрямую возвращается, преобразуется в замену кадра в стеке (вместо суммирования), эффективно «выравнивая» рекурсивный вызов функции в цикле и устраняя рекурсивную функцию. звонки. Это делает отладку немного сложнее, потому что нет вызовов функций там, где вы ожидаете их, соответственно. вы не знаете, как «глубоко» в рекурсии происходит ошибка (как если бы вы написали цикл для начала). Ваша среда может сделать некоторые декларации по умолчанию, которые необходимо переопределить, чтобы включить TCO.

edit: Просто вернемся к этому вопросу, что такое g? Я думаю, что вы действительно хотите

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

Answer 2

Я предполагаю, что есть встроенный предел глубины стека с lispbox. Так как Common Lisp не гарантирует, что хвостовые рекурсивные функции используют постоянное пространство стека, возможно, что каждый вызов дробно-уменьшенных дробей добавляет в стек еще один слой.

Кстати, SBCL запускает этот алгоритм без проблем.

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

* (count-reduced-fractions 100 100 0)
3043

Answer 3

По стилю вы можете сделать d и sum необязательными.

(defun test (n &optional (d n) (sum 0)) .. )

Answer 4

Возможно переполнение стека (хе).