Functional Python Programming

Recursions and Reductions

Stepping outside purely functional processing, we can define an imperative facti()
calculation as follows:

def facti(n):
if n == 0: return 1
f= 1
for i in range(2,n):
f= f*i
return f

This version of the factorial function will compute values beyond 1000! (2000!,
for example, has 5733 digits). It isn't purely functional. We've optimized the tail
recursion into a stateful loop depending on the i variable to maintain the state
of the computation.

In general, we're obliged to do this in Python because Python can't automatically
do the tail-call optimization. There are situations, however, where this kind of
optimization isn't actually helpful. We'll look at a few situations.

Leaving recursion in place

In some cases, the recursive definition is actually optimal. Some recursions involve

a divide and conquer strategy that minimizes the work from On() to On()log 2. One
example of this is the exponentiation by the squaring algorithm. We can state it
formally like this:

()

1

/2^2

1 0

n n

n

n

aa an

an

−

 =



=×





if

if is odd

if is even

We've broken the process into three cases, easily written in Python as a recursion.
Look at the following command snippet:

def fastexp(a, n):

if n == 0: return 1

elif n % 2 == 1: return a*fastexp(a,n-1)

else:

t= fastexp(a,n//2)

return t*t