Реализация чисел Фибоначчи с помощью хвостовой рекурсии в Haskell

#функции #рекурсия #haskell #функциональное_программирование

Решаю задачу с рядом фибоначчи (+ отрицательные). Приблизительно так:

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n | n == 0 = 1
                 | n > 0 = fibonacci (n - 1) + fibonacci (n - 2)
                 | n < 0 = fibonacci (n + 2) - fibonacci (n + 1)


нужно увеличить скорость просчета. для этого естественно нужен аккумулятор.

Как это сделать?
    

Ответы

Ответ 1

Правильнее всего, конечно, использовать готовую формулу n-ого члена :) Но для случая,
когда нужно находить программным путём, подходит следующая идея (пишу алгоритм, не
знаю синтаксис Хаскеля):

fib n = helper 0 1 n
  where helper curr prev n
          | n == 0   = curr
          | n > 0    = helper (curr+prev) curr (n-1)
          | n < 0    = helper prev (curr-prev) (n+1)


Это вычисляет последовательность за линейное время с хвостовой рекурсией.