Chapter 6Without these constraints. a-1 can't be guaranteed to approach the nonrecursive case
of a == 0.
In most cases, this is obvious. In a few rare cases, it might be difficult to prove.
One example is the Syracuse function. This is one of the pathological cases where
termination is unclear.
Implementing tail-call optimization
In the case of some functions, the recursive definition is the one often stated
because it is succinct and expressive. One of the most common examples is the
factorial() function.
We can see how this is rewritten as a simple recursive function in Python from the
following formula:
()(^10)
!
1! 0
n
n
nn n
=
=
×− >
if
if
The preceding formula can be executed in Python by using the following commands:
def fact(n):
if n == 0: return 1
else: return n*fact(n-1)
This has the advantage of simplicity. The recursion limits in Python artificially
constrain us; we can't do anything larger than about fact(997). The value of 1000! has
2,568 digits and generally exceeds our floating-point capacity; on some systems this
is about 10300 Pragmatically, it's common to switch to a log gamma function, which
works well with large floating-point values.
This function demonstrates a typical tail recursion. The last expression in the function
is a call to the function with a new argument value. An optimizing compiler can
replace the function call stack management with a loop that executes very quickly.
Since Python doesn't have an optimizing compiler, we're obliged to look at scalar
recursions with an eye toward optimizing them. In this case, the function involves
an incremental change from n to n-1. This means that we're generating a sequence
of numbers and then doing a reduction to compute their product.