Does Python Optimize Tail Recursion

Does Python optimize tail recursion?

No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:

Tail Recursion Elimination (2009-04-22)

Final Words on Tail Calls (2009-04-27)

You can manually eliminate the recursion with a transformation like this:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500

change the recursive function to tail recursive

As mentioned in the comment and discussed further in this answer python does not have tail recursion optimization.

Other languages such as Haskell do support tail recursion.
this function could be rewritten in Haskell in as a tail recursive function like this:

singlesR = singlesR' []
  where singlesR' acc [] = acc
        singlesR' acc (x:xs) = singlesR' ([x]:acc) xs

The main observation here is that in the tail recursive version all of the work is done inside of the recursive call.

Tail-Recursion Optimization Decorator in Python

without tail call optimization your stack looks like this:

factorial(10000)
factorial(9999)
factorial(9998)
factorial(9997)
factorial(9996)
...

and grows until you reach sys.getrecursionlimit() calls (then kaboom).

with tail call optimization:

factorial(10000,1)
factorial(9999,10000) <-- f.f_back.f_back.f_code = f.f_code? nope
factorial(9998,99990000) <-- f.f_back.f_back.f_code = f.f_code? yes, raise excn.

and the exception makes the decorator go to the next iteration of its while loop.

Is it advisable to write recursive functions in Python

2) Is there any way I can circumvent this limitation assuming that I can live without a stack-trace.
I ask this because Verilog mainly deals with state-machines which can be implemented in an elegant way using recursive functions.

There is a way to avoid tail calls without changing your existing logic too much, simply rewrite your tail calls to return a thunk and use a trampoline to call that thunk. If you need to pass in complex state between transition, you can use continuation passing style to pass them around. This style of writing code is very well suited for writing a state machine.

An example is perhaps clearer, suppose that you start with this recursive implementation of a fizzbuzz state machine that uses tail calls to pass control to the next transition:

def start():
    return increment(0)

def fizz(n):
    print 'fizz'
    return increment(n)

def buzz(n):
    print 'buzz'
    return increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return increment(n)

def increment(n):
    n = n + 1
    if n > 100:
        return terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return fizzbuzz(n)
    elif n % 3 == 0: 
        return fizz(n)
    elif n % 5 == 0:
        return buzz(n)
    else:
        print n
        return increment(n)

def terminate():
    raise StopIteration

try:
    start()
except StopIteration:
    pass

To avoid the tail calls, you simply wrap all the tail calls in lambda (or alternatively, functools.partial) and add a trampoline:

def start():
    return lambda: increment(0)

def fizz(n):
    print 'fizz'
    return lambda: increment(n)

def buzz(n):
    print 'buzz'
    return lambda: increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return lambda: increment(n)

def increment(n):
    n = n + 1
    if n > 2000:
        # strictly speaking, transitions that takes no arguments
        # like terminate don't need to be wrapped in lambda
        # this is added here only for symmetry with others
        return lambda: terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return lambda: fizzbuzz(n)
    elif n % 3 == 0: 
        return lambda: fizz(n)
    elif n % 5 == 0:
        return lambda: buzz(n)
    else:
        print n
        return lambda: increment(n)

def terminate():
    raise StopIteration

def trampoline(func): 
    try:
        while True:
            func = func()
    except StopIteration:
        pass

trampoline(lambda: start())

Now you can have lots more fizzbuzz without hitting the recursion limit.

Why is Python recursion so expensive and what can we do about it?

A solution is a trampoline: the recursive function, instead of calling another function, returns a function that makes that call with the appropriate arguments. There's a loop one level higher that calls all those functions in a loop until we have the final result. I'm probably not explaining it very well; you can find resources online that do a better job.

The point is that this converts recursion to iteration. I don't think this is faster, maybe it's even slower, but the recursion depth stays low.

An implementation could look like below. I split the pair x into a and b for clarity. I then converted the recursive function to a version that keeps track of a and b as arguments, making it tail recursive.

def fib_acc(n, a, b):
    if n == 1:
        return (a, b)
    return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997)

def fib(n):
    x = fib_acc(n, 1, 2)
    while callable(x):
        x = x()
    return x

if __name__=='__main__':
    print(fib(50000)[0])

Python tail recursion optimization in this algo?

You care about the recursion depth, i.e. the maximum depth (height?) of the call stack.

Here's an empirical approach: (code that measures the depth)

import string, sys
sys.setrecursionlimit(100)  # limit the number of recursions to 100

dict_values = dict(zip(range(26), string.ascii_lowercase))
stack = []
max_depth = 0
def count_split(list_numbers: list) -> int:
    global max_depth
    stack.append(None)
    max_depth = max(max_depth, len(stack))
    if len(list_numbers) == 0:
        return 0

    elif len(list_numbers) == 1:
        return 1

    elif len(list_numbers) == 2:
        if int(list_numbers[0]) == 0:
            return 1

        elif 10 <= int("".join(list_numbers)) <= 25:
            return 2

        else:
            return 1

    else:  # list_numbers contains at least three elements
        if count_split(list_numbers[:2]) == 2:
            stack.pop()
            result = count_split(list_numbers[1:]) + count_split(list_numbers[2:])
            stack.pop(); stack.pop()
            return result

        else:
            result = count_split(list_numbers[1:])
            stack.pop()
            return result

def get_nb_words(code: str) -> int:
    return count_split(list(code))

print(get_nb_words("12121212121212121212"))
print(max_depth) # 20

What is tail call optimization?

Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization, so here are two examples of the factorial function in Scheme:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

The first function is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns. As such, the stack looks as follows:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

In contrast, the stack trace for the tail recursive factorial looks as follows:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

As you can see, we only need to keep track of the same amount of data for every call to fact-tail because we are simply returning the value we get right through to the top. This means that even if I were to call (fact 1000000), I need only the same amount of space as (fact 3). This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow.

---

Related Topics