[已解决]有关递归函数的空间复杂度

白牡丹秀色可餐

1 int x(int n)
2 {
3     if(n<=3)
4     {
5         return 1;
6     }
7     else
8     {
9         return x(n-2)+x(n-4)+1;
10     }
11 }

有人解释说空间复杂度是递归次数，时间复杂度是调用函数的次数，但我还是不太明白递归次数应该怎么算，x(n-2)和x(n-4)不是各自都递归了吗是不是算是两次递归，那这样的话空间复杂度应该是O（2^n）,但是答案是O（n）。
我就是没办法理解这一点，递归次数和调用函数次数有什么不同，递归次数应该怎么算？

最佳答案

月排行榜 / 总排行榜

赚小钱

2020-6-9 01:23:47

时间复杂度，计算总共耗时
空间复杂度，当前占用的空间规模。

在代码 L:9 出，函数调用有先后关系，并且，为同步调用(不是并行)。
因此，假设，执行顺序从左到右(或者从右到左，都不影响)，先计算 x(n-2)，当执行结束之后，额外的递归调用栈空间被回收，然后再执行 x(n-4)。

因此，对于函数 x 而言，空间复杂度，就是递归函数调用的深度。
即，O(n)。

跳转到最佳答案楼层

赚小钱

时间复杂度，计算总共耗时
空间复杂度，当前占用的空间规模。

在代码 L:9 出，函数调用有先后关系，并且，为同步调用(不是并行)。
因此，假设，执行顺序从左到右(或者从右到左，都不影响)，先计算 x(n-2)，当执行结束之后，额外的递归调用栈空间被回收，然后再执行 x(n-4)。

因此，对于函数 x 而言，空间复杂度，就是递归函数调用的深度。
即，O(n)。