空间复杂度

下面这段代码 take O(n) time and O(n) space

However, just because you have n calls total doesn't mean it takes O(n) space

There will be roughly O(n) calls to pairSum. However, those calls do not exist simultaneously on the call stack (并没有立即作用在调用栈上面), so you only need O (1) space.

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

The space complexity of this algorithm will be O(N)