Coconut-enabled Improvements: Automatic Tail Call Optimization

Here's where we left off:

def factorial(n):
    """Compute n! where n is an integer >= 0."""
    case n:
        match 0:
            return 1
        match _ is int if n > 0:
            return n * factorial(n-1)
    else:
        raise TypeError("the argument to factorial must be an integer >= 0")

# Test cases:
-1 |> factorial |> print  # TypeError
0.5 |> factorial |> print  # TypeError
0 |> factorial |> print  # 1
3 |> factorial |> print  # 6

Coconut can perform automatic tail call optimization, which means that whenever a function directly returns a call to another function, Coconut will optimize away the additional call. Thus, we can improve our factorial function by rewriting it to use a tail call.

In the function definition, factorial will now have two arguments: n and acc=1. Change the definition of factorial to include both.

If n matches the 0 pattern, we should return acc. When n=0, acc is the desired result of n factorial. That’s why we initialized it to equal 1. Make the function return acc instead of 1 if n matches 0.

If n matches the wildcard pattern, we should return n times the call to factorial again, but with the appropriate number of arguments. The first argument should stay the same: n-1. Make the second argument acc*n. The expression acc*n calculates n factorial.

The benefit of this is that the function will never raise a RuntimeError because it will never reach Python’s maximum recursion depth.

Run the code to make sure the test cases pass!

Show Solution:


Next
Previous