所有的递归算法空间复杂度都是O(n)吗?? ?

比如说这个: function f(a,b){ if(a===1) return b; else return f(a-1,b); } 这个空间复杂度是O(1)还是O(n)
关注者
89
被浏览
13,784

6 个回答

转自知乎某匿名用户

一般的递归 
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)


输入5 
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15


尾递归 
def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)
输入5 
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
尾递归在于不在栈中新创建状态，而是覆盖当前状态。但是不是所有的编译器都支持这种优化。楼主你的函数是属于尾递归的，但是空间复杂度却不一定是n(1)
递归计算一个数组的和也有可能是O(1)复杂度： 

int Sum(int[] numbers, int start, int sum)
    if(start>=numbers.Length) return sum;
    if (start < 2) return Sum(numbers, start+1, sum+numbers[start]);
    for(int i=start;i<numbers.Length;i++)