TailRecursiveFibonacci

尾遞迴費氏數列

費氏數列，又稱黃金分割數列，是自然界中非常常見的數列。它是由以下遞迴式所定義：

產生以下數列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

由單純的遞迴演算法會造成函式呼叫堆積在記憶體中，造成堆疊溢位（stack overflow）。我們可以設法減少需要呼叫的函數目降造成堆疊溢位的可能性，如此可以計算更大的費氏數列。在原本的遞迴費氏數列中會呼叫兩個函式來計算費氏數列，像是 fib(n-1) + fib(n-2)，如此會佔去兩個函式的空間。我們可以藉由函式後方累積的數字來作為一個紀錄，並且將要計算的數字遞減，來減少所需要的函式呼叫。如以下概念：

fib(n, 1, 0) -> fib(n-1, 1, 1)
fib(n-1, 1, 1) -> fib(n-2, 2, 1)
fib(n-2, 2, 1) -> fib(n-3, 1, 1)
...
fib(1, fib[n], fib[n-1])

範例：尾遞迴加法

這邊提供一個尾遞迴加法的例子作為參考。

function sum(n, acc)
    if n == 0
        return acc
    else
        return sum(n-1, acc+n)
    end
end

sum(5, 0)  # 15
sum(10, 0)  # 55
sum(5, 1)  # 16
sum(10, 1)  # 56

測試

@test fib(0, 1, 0) .== 0
@test fib(1, 1, 0) .== 1
@test fib(2, 1, 0) .== 1
@test fib(4, 1, 0) .== 3

測試資料

fib(0, 1, 0)
fib(1, 1, 0)
fib(2, 1, 0)
fib(4, 1, 0)
fib(10, 1, 0)
fib(50, 1, 0)
fib(100, 1, 0)