Does the python stack grow with an iterative process that is executed by a recursive procedure?

Question

I know that Python doesn't support tail-call optimization. Does that mean a recursive procedure with an iterative process like the factorial I defined below would consume O(n) memory, or does the fact that there are no deferred operations mean that space would be O(1)?

def factorial(n, accum=1):
    if n == 0:
        return accum
    else:
        return factorial(n-1, accum * n)

Answer 1

The memory will be O(n). If python optimized that case, then an exception that happened deep in the recursion wouldn't have a full stack trace. You can test for yourself that it does by just making the base case raise an exception, and you will see the full stack trace.

Answer 2

No tail-call optimization means that you need to keep the stack in memory before the recursive call returns, so it seems to me that the memory usage would be O(n) in this case.

If you want to check it out by yourself, just running your example code for large values of n (with use of sys.setrecursionlimit) and checking the memory usage in top should convince you that this not O(1).