Space Complexity

Space complexity is given by two contributions:

1. The size of the stack used to keep track of recursive calls: return address of the function, parameters, local variables of the function.
2. Non recursion related (such as memoization): global variables, intermediate results, memoization.