空間複雜遞歸

Question

對於一個簡單的程序：

public class solution{ 
    public void start(int m, int n){ 
     for(int i = 0; i < m; i++) 
      recur(n); 
    } 

    public void recur(int n){ 
     for(int j = 0; j < n; j++) 
      recur(n-1); 
    } 
} 

誰能幫我分析，空間複雜度？我認爲它是O（m * n）。

感謝。

Answer 1

調用堆棧永遠不會超過O（n）多個元素，所以這就是空間複雜度。遞歸樹的每個分支都將被處理，而其他分支上的其他元素不會佔用任何空間，並且樹的深度爲O（n），所以我們需要多少空間。