мета-данные страницы
Это старая версия документа!
Числа Фиббоначи
Рассмотрим лобовое решение с бинарной рекурсией:
fib :: Int -> Int fib 1 = 1 fib 2 = 1 fib n = fib (n-1) + fib (n-2)
тогда сам список чисел Фиббоначи может быть задан следующим образом:
fibset = [ fib n | n <- [1..] ]
Однако данный способ вычисления является хоть и простым, но крайне затратным, так как вынужден делать бинарное дерево ветвлений вычислений при рекурсивном спуске. При этом хотя все вычисления одинаковые, но они делаются независимо и вынуждены занимать всю доступную память. Таким образом, на некоторых компьютерах вычислить даже 40-й элементы последовательности является проблематичным, а 45-й, тем более 50-й вычислить нереально практически на всех доступных персональных компьютерах.