Space Complexity for Recursion

Question

For a simple program:

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

Could anyone help me analysis the space complexity? I think it is O(m*n).

Thanks.

Answer 1

The call stack will never exceed O(n) many elements, so that's the space complexity. Every branch of the recursion tree will be processed while no other elements that only lie on other branches take up any space, and the tree's depth is O(n), so that's how much space we need.