Date: 2020-10-02 07:08 (UTC)
vak: (0)
From: [personal profile] vak
Ой, действительно! Исправил.

Проблема с этим вариантом вычисления Фибоначчи, что даже сотый элемент не удаётся получить за разумное время.
Переписал на конечную рекурсию:
(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". Всё потому, что Питоновская виртуальная машина не поддерживает конечную рекурсию.

Переписал итеративным образом:
(defn fib [index]
    (if (< index 0)
        (raise (ValueError "Negative input to Fibonacci!")))
    (if (< index 2)
        (return index))
    (setv prev2 0)
    (setv prev1 1)
    (for [iteration (range 1 index)]
        (setv sum (+ prev2 prev1))
        (setv prev2 prev1)
        (setv prev1 sum))
    sum)

(print "(fib 1000) =" (fib 1000))
Теперь даже до миллионного элемента работает. Но всякий интерес пропадает: итеративный код проще будет на обыкновенном Питоне написать.
This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org