java - 递归的空间复杂度

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)，因此这就是我们需要的空间。