Проблема с реализацией Фибоначчи на Хаскеле

Question

Только что начал переучивать Haskell (делал это в универе, но забыл большую часть) и думал, что я начну с функции Фибоначчи. Тем не менее, я продолжаю получать переполнение стека, даже для очень маленьких n.

Может кто-нибудь заметить какие-либо проблемы с моей функцией?

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n+1)

Answer 1

В вашей формуле Фибоначчи есть ошибка:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Обратите внимание на самый последний член, где вместо n+1.

стоит n-2.

Answer 2

Это очень плохая реализация, вы должны использовать хвостовую рекурсию, начиная с 0 или 1, идя вверх и пропуская два предыдущих числа Фибоначчи.Также есть ошибка, Fib n зависит от FIB N + 1.

fib :: Integer -> Integer
fib 0 = 0
fib n = iter 0 1 n
  where iter :: Integer -> Integer -> Integer -> Integer
        iter f1 f2 0 = f2
        iter f1 f2 n = iter f2 (f1+f2) (n-1)