I am reading tail recursion from tail recursion - LeetCode
It state that python do not support tail recursion optimization
A tail recursion function can be executed as non-tail-recursion functions, i.e. with piles of call stacks, without impact on the result. Often, the compiler recognizes tail recursion pattern, and optimizes its execution. However, not all programming languages support this optimization. For instance, C, C++ support the optimization of tail recursion functions. On the other hand, Java and Python do not support tail recursion optimization.
I do not get the idea what tail recursion optimization
mean.
The tutorial provide an example
def sum_non_tail_recursion(ls):
"""
:type ls: List[int]
:rtype: int, the sum of the input list.
"""
if len(ls) == 0:
return 0
# not a tail recursion because it does some computation after the recursive call returned.
return ls[0] + sum_non_tail_recursion(ls[1:])
def sum_tail_recursion(ls):
"""
:type ls: List[int]
:rtype: int, the sum of the input list.
"""
def helper(ls, acc):
if len(ls) == 0:
return acc
# this is a tail recursion because the final instruction is a recursive call.
return helper(ls[1:], ls[0] + acc)
return helper(ls, 0)
and illustrate
Note that in tail recursion, we know that as soon as we return from the recursive call we are going to immediately return as well, so we can skip the entire chain of recursive calls returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, which saves us space.
For example, in step (1), a space in the stack would be allocated for
f(x1)
in order to callf(x2)
. Then in step (2), the functionf(x2)
would recursively callf(x3)
. However, instead of allocating new space on the stack, the system could simply reuse the space allocated earlier for this second recursion call. Finally, in the functionf(x3)
, we reach the base case, and the function could simply return the result to the original caller without going back to the previous function calls.
The key idea here is that we can skip the entire chain of recursive calls and reuse the space allocated earlier.
As for python does not support tail recursion optimization.
Does it mean that python will still need a call stack and don't reuse the earlier allocated space in a tail recursion?