Можно ли сгенерировать более 40000 элементов Фибоначчи в Лиспе?

Question

Я пытаюсь решить Project Euler вопрос 2 с помощью Lisp. Это рекурсивное решение уничтожает стек при выполнении, но я думал, что Lisp (используя clisp) распознает хвостовую рекурсию. Это вводится в верхний уровень.

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"

   (if (> f2 4000000) sum)
   (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                (+ sum f2) 
                               sum))

Правильно ли настроена моя реализация для оптимизации? Я полагаю, что это немного помешало бы моему образованию на Лиспе, если бы я не мог полагаться на идиоматическую рекурсию.

Answer 1

Рекурсия (или даже итерация) не нужна!

Каждое третье число Фибоначчи чётно:

1 1 2 3 5 8 13 21 34 55 89 144 ...

и поскольку каждое четное число Фибоначчи (выделено жирным шрифтом) является суммой двух предшествующих нечетных чисел Фибоначчи, сумма четных чисел Фибоначчи вплоть до F _n - это ровно половина суммы всех чисел Фибоначчи до F _n (если F _n четно, конечно).

Теперь сумма первых n чисел Фибоначчи равна F _{n + 2} - 1. Это легко проверить по индукции: сумма первые n + 1 числа Фибоначчи - это F ₁ + F ₂ + ... + F _n + F _{n + 1} , что равно F _{n + 2} - 1 + F _{n + 1} по гипотезе, что равно F _{n + 3} - 1 по определению чисел Фибоначчи.

Так что, если вы можете найти наибольшее N такое, что F _{3 N} ≤ 4 000 000, тогда запрашиваемая сумма будет (F _{3 N + 2} - 1) / 2 * 1 083 *

(я оставлю вам остальные детали, но здесь все будет просто.)

Answer 2

1) Правильный синтаксис ошибка в коде:

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (if (> f2 4000000) 
       sum   ;; here was a closing bracket 
       (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                    (+ sum f2) 
                                    sum))))  ;; 2 more brackets here

2) использование SBCL .CLISP не достаточно любезен, чтобы обнаружить хвостовую рекурсию.

3) использовать максимально возможную оптимизацию уровень:

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (declare (optimize (debug 0)))  ;; optimization
   ... 

Answer 3

Я думал, что Лисп (используя clisp) распознает хвостовую рекурсию

Для среды, в которой устранение хвостовых вызовов является обязательным в схеме , но не в большинстведругие диалекты Лисп, такие как Common Lisp.

Answer 4

Ваш код реализует бесконечный цикл. Не заканчивается.

Использование LOOP:

(defun e2-problem-a (n)
  "Sum fibonacci sequence, even terms up to n"
  (loop for f1 = 1 then f2
        and f2 = 1 then (+ f1 f2)
        while (<= f2 n)
        when (evenp f2) sum f2))