所有的遞歸演算法空間複雜度都是O(n)嗎?? ?

比如說這個:

function f(a,b){

if(a===1) return b;

else return f(a-1,b);

}

這個空間複雜度是O(1)還是O(n)

轉自知乎某匿名用戶

def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)


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&