Пространственная сложность последовательности Фибоначчи

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 

Есть 4 c, когда n = 5. В общем, есть n-1 c.