Recursive functions memory usage

Question

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.

I read about Guppy-PE, but I didn't get very well how to use it. — João Paulo, Dec 19 '14 at 11:16
I'd like to know about the recursive thing too, I don't think its a duplicate. — João Paulo, Dec 19 '14 at 11:19

score 4 · Accepted Answer · answered Dec 19 '14 at 12:09

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/

Recursive functions memory usage

1 Answers1