Functional Python Programming

Chapter 6

This function has three cases. The base case, the fastexp(a, 0) method is defined
as having a value of 1. The other two cases take two different approaches. For odd
numbers, the fastexp() method is defined recursively. The exponent, n, is reduced
by 1. A simple tail-recursion optimization would work for this case.

For even numbers, however, the fastexp() recursion uses n/2, chopping the
problem into half of its original size. Since the problem size is reduced by a factor
of 2, this case results in a significant speed-up of the processing.

We can't trivially reframe this kind of function into a tail-call optimization loop. Since
it's already optimal, we don't really need to optimize this further. The recursion limit in
Python would impose the constraint of n≤ 21000 , a generous upper bound.

Handling difficult tail-call optimization

We can look at the definition of Fibonacci numbers recursively. Following is one
widely used definition for the nth Fibonacci number:

1 2

0 0

1 1

2

n

nn

n

F n

FF−− n

 =



= =

 + ≥



if

if

if

A given Fibonacci number, Fn, is defined as the sum of the previous two numbers,
FFnn−−1 2+. This is an example of multiple recursion: it can't be trivially optimized as a
simple tail-recursion. However, if we don't optimize it to a tail-recursion, we'll find it
to be too slow to be useful.

The following is a naïve implementation:

def fib(n):

if n == 0: return 0

if n == 1: return 1

return fib(n-1) + fib(n-2)

This suffers from the multiple recursion problem. When computing the fib(n)
method, we must compute fib(n-1) and fib(n-2) methods. The computation of
fib(n-1) method involves a duplicate calculation of fib(n-2) method. The two
recursive uses of the Fibonacci function will duplicate the amount of computation
being done.

Because of the left-to-right Python evaluation rules, we can evaluate values up to
about fib(1000). However, we have to be patient. Very patient.