斐波那契數列的空間複雜度

Question

我看到一些關於斐波那契數列的最壞情況空間複雜度的教科書。不過，我有以下問題：

Answer 1

你可以用一個具體的例子啓動和推廣。從n = 5開始。

S(5) = S(4) + c 
    = (S(3) + c) + c 
    = ((S(2) + c) + c) + c 
    = (((S(1) + c) + c) + c) + c 

    = S(1) + 4c 

當n = 5時有4個c。一般來說，有n-1個c's。