space 斐波那契数列的复杂性

Question

我看过一些关于斐波那契数列最坏情况 space 复杂度的教科书。但是，我有以下问题：

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。

The space complexity of Fibonacci Sequence