pythonmemoryrecursion

Recursive functions memory usage

I have here a recursive function:

def pow(x, n):
    if n == 0:
       return 1
    else:
       return x * pow(x, n-1)
answer = pow(a, b)

And an iterative:

def pow(x, n): # n != 0
    answer = x
    while n > 1:
        answer *= x
        n -= 1
    return answer
answer = pow(a, b)

I'd like to know which one of the them use more memory. I think recursively uses more memory because it keeps 'variables' passed for each function call. If that's right, what would be an formalism to explain this? Is there a nice way to track this memory usage inside code?

I don't think It's a duplicate. The main question isn't about track the memory usage, but It's about the recursive memory usage.

Solution

  • No formalism is needed here.

    Python stack frames are huge.

    Your recursive code is using a lot more memory.

    Typical CPython stack frame is over 50 elements plus local variables, taking x86_64 architecture as an example, that's almost 500 bytes.

    In [1]: import inspect

In [2]: inspect.stack()[1][0]
Out[2]: <frame at 0x7fed81c86850>

In [3]: inspect.stack()[1][0].__sizeof__()
Out[3]: 472

    Good post about frame content: http://tech.blog.aknin.name/2010/07/22/pythons-innards-interpreter-stacks/