Menu
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)
447
Recursion is when a function calls itself within its code, thus repeatedly executing the instructions present inside it. Iteration is when a loop repeatedly executes the set of instructions like "for" loops and "while" loops.
Recursion vs Iteration Since Python does not store anything about previous iteration steps, iteration is quite faster and memory-efficient than recursion.
Initialize the accumulator before the while-loop. Use the negation of the base-case condition as the loop's condition. Use the recursive function's body (except the recursive call) as the body of the while-loop. After the loop, apply the base-case update of the accumulator and return its value.
One way to break out of a recursive function in Python is to throw an exception and catch that at the top level. Some people will say that this is not the right way to think about recursion, but it gets the job done.
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.
174
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).
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
