In Chapter 6, Recursions and Reductions, among many others, we looked at how a simple recursion can be optimized into a for loop. We'll use the following simple recursive definition of factorial as an example:
The general approach to optimizing a recrusion is this:
- Design the recursion. This means the base case and the recursive cases as a simple function that can be tested and shown to be correct, but slow. Here's the simple definition:
def fact(n: int) -> int:
if n == 0: return 1
else: return n*fact(n-1)
- If the recursion has a simple call at the end, replace the recursive case with a for loop. The definition is as follows:
def facti(n: int) -> int:
if n == 0: return 1
f = 1
for i in range(2,n):
f = f*i
return f
When the recursion appears at the end of a simple function, it's described as...
