1

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

img

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 call f(x2). Then in step (2), the function f(x2) would recursively call f(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 function f(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?

Jon
  • 91
  • 9
  • 1
    From what I understand, yes, python will store all calls in a stack, even if the function can be optimised to be essentially iterative, but who am I. I think a good answer can be found here: https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion – Recessive Apr 18 '19 at 01:14
  • 1
    To tail recursion to work the last expression of a function need to be a call to another function where all arguments are already satisfied. This means that the caller doesn't have anything more to do, imagine something like this `def foo(): return bar()`; there is nothing on `foo` to be done when it calls `bar`. So in this case, instead of creating a new stack frame, the interpreter/compiler/whatever can simply jump to the next function. This make possible to achieve infinite recursion – geckos Apr 18 '19 at 01:22
  • 1
    thank you.tail recursion is amazing which produce an illusion that a programmer can jump instantly to the final base case without any intermediate steps. @Recessive – Jon Apr 18 '19 at 01:26
  • 1
    I hope that one day we'll have TCO in python! – geckos Apr 18 '19 at 01:30

0 Answers0