Space 递归的复杂性

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);
    }
}

谁能帮我分析一下 space 的复杂性？我认为是 O(m*n).

谢谢。

Answer 1

调用堆栈永远不会超过 O(n) 个元素，所以这就是 space 的复杂性。递归树的每个分支都将被处理，而仅位于其他分支上的其他元素不会占用任何 space，并且树的深度为 O(n)，所以这就是我们需要的 space。