Проблема с этим вариантом вычисления Фибоначчи, что даже сотый элемент не удаётся получить за разумное время. Переписал на конечную рекурсию:
(defn fib [index]
(if (< index 0)
(raise (ValueError "Negative input to Fibonacci!")))
(if (< index 2)
(return 1))
(defn fibrec [index iteration prev2 prev1]
(setv sum (+ prev2 prev1))
(setv iter1 (+ iteration 1))
(if (= iter1 index)
(return sum))
(fibrec index iter1 prev1 sum))
(fibrec index 1 0 1))
(print "(fib 100) =" (fib 100))
Теперь до 900-того вычисляет, а на 1000-ном падает с ошибкой "RecursionError: maximum recursion depth exceeded". Всё потому, что Питоновская виртуальная машина не поддерживает конечную рекурсию.
no subject
Date: 2020-10-02 07:08 (UTC)Проблема с этим вариантом вычисления Фибоначчи, что даже сотый элемент не удаётся получить за разумное время.
Переписал на конечную рекурсию:
Теперь до 900-того вычисляет, а на 1000-ном падает с ошибкой "RecursionError: maximum recursion depth exceeded". Всё потому, что Питоновская виртуальная машина не поддерживает конечную рекурсию.
Переписал итеративным образом:
Теперь даже до миллионного элемента работает. Но всякий интерес пропадает: итеративный код проще будет на обыкновенном Питоне написать.