有关递归函数的空间复杂度
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）。
我就是没办法理解这一点，递归次数和调用函数次数有什么不同，递归次数应该怎么算？ 时间复杂度，计算总共耗时
空间复杂度，当前占用的空间规模。
在代码 L:9 出，函数调用有先后关系，并且，为同步调用(不是并行)。
因此，假设，执行顺序从左到右(或者从右到左，都不影响)，先计算 x(n-2)，当执行结束之后，额外的递归调用栈空间被回收，然后再执行 x(n-4)。
因此，对于函数 x 而言，空间复杂度，就是递归函数调用的深度。
即，O(n)。
页:
[1]