Functional Python Programming

Chapter 16

• Design the recursion. This means the base case and the recursive cases.
  For example, this is a definition of computing:

nn!=×()n− 1!

To design the recursion execute the following commands:

def fact(n):

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 command is as follows:

def facti(n):

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 a tail–call optimization. Many compilers will optimize this into a loop.
Python—lacking this optimization in its compiler—doesn't do this kind
of tail-call transformation.

This pattern is very common. Performing the tail-call optimization improves
performance and removes any upper bound on the number of recursions that
can be done.

Prior to doing any optimization, it's absolutely essential that the function already
works. For this, a simple doctest string is often sufficient. We might use annotation
on our factorial functions like this:

def fact(n):

"""Recursive Factorial

fact(0)

1

fact(1)

1

fact(7)

5040