Recurcion.hs

module Recurcion  where
{-
Последовательность чисел Фибоначчи 0,1,1,2,3,5,8,13,21,… легко определить рекурсивно, задав два первых терминирующих
значения и определив любое последующее как сумму двух непосредственно предыдущих.

На Haskell данное определение задаётся следующей функцией:

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

Эта функция определена лишь для неотрицательных чисел. Однако, из данного выше определения можно вывести формулу для
вычисления чисел Фибоначчи при отрицательных индексах, при этом последовательность будет следующей:

F_{−1}=1, F_{−2}=−1,…,F_{−10}=−55,…

Измените определение функции fibonacci так, чтобы она была определена для всех целых чисел и порождала при отрицательных
аргументах указанную последовательность.
-}
fibonacci :: Integer -> Integer
fibonacci n
    | n == 0 = 0
    | n == 1 = 1
    | n == -1 = 1
    | n < 0  = if not (even n) then fibonacci (-n) else (-fibonacci (-n))
    | otherwise = fibonacci (n - 1) + fibonacci (n - 2)
{-
Реализация функции для вычисления числа Фибоначчи, основанная на прямом рекурсивном определении, крайне неэффективна -
количество вызовов функции растет экспоненциально с ростом значения аргумента. GHCi позволяет отслеживать использование
памяти и затраты времени на вычисление выражения, для этого следует выполнить команду :set +s:

GHCi> :set +s
GHCi> fibonacci 30
832040
(8.36 secs, 298293400 bytes)

С помощью механизма аккумуляторов попробуйте написать более эффективную реализацию, имеющую линейную сложность (по числу
рекурсивных вызовов). Как и в предыдущем задании, функция должна быть определена для всех целых чисел.
-}
fibonacci' :: Integer -> Integer
fibonacci' n
    | n == 0 = 0
    | n == 1 = 1
    | n == -1 = 1
    | n < 0  = if not (even n) then fibonacci'' 0 1 (-n) else (-fibonacci'' 0 1 (-n))
    | otherwise = fibonacci'' 0 1 n

fibonacci'' a b 0 = a
fibonacci'' a b n = fibonacci'' b (a + b) (n - 1)