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
– João Paulo, Commented Dec 19, 2014 at 11:16
I'd like to know about the recursive thing too, I don't think its a duplicate. — João Paulo
– João Paulo, Commented Dec 19, 2014 at 11:19

Dima Tisnek · Accepted Answer · 2014-12-19 12:09:41Z

5

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/

answered Dec 19, 2014 at 12:09

Dima Tisnek

11.9k4 gold badges73 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursive functions memory usage

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related