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!