递归的空间复杂性

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),因此我们需要多少空间.