Memory usage of recursive functions
I have a recursive function here:
def pow(x, n):
if n == 0:
return 1
else:
return x * pow(x, n-1)
answer = pow(a, b)
Iterative:
def pow(x, n): # n != 0
answer = x
while n > 1:
answer *= x
n -= 1
return answer
answer = pow(a, b)
I would like to know which one is using more memory. I think it uses more memory recursively because it stores "variables" for every function call. If this is correct, what would be the formalism to explain this? Is there a good way to track the usage of this memory inside the code?
I don't think this is a duplicate. The main issue is not about keeping track of memory usage, but about recursive memory usage.
source to share
There is no formalism here.
Python stack frames are huge .
Your recursive code uses a lot more memory.
A typical CPython stack frame contains over 50 elements plus local variables, using the x86_64 architecture as an example, which is 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
Nice post about frame content: http://tech.blog.aknin.name/2010/07/22/pythons-innards-interpreter-stacks/
source to share