Recursions and Reductions
Simple numerical recursions
We can consider all numeric operations to be defined by recursions. For more
depth, read about the Peano axioms that define the essential features of numbers.
http://en.wikipedia.org/wiki/Peano_axioms is one place to start.
From these axioms, we can see that addition is defined recursively using more
primitive notions of the next number, or successor of a number, n, Sn().
To simplify the presentation, we'll assume that we can define a predecessor function,
Pn(), such that nS==()Pn() PS()()n , as long as n≠ 0
Addition between two natural numbers could be defined recursively as follows:
()
()() ()0
add,
add, 0b a
ab
Pa Sb a =
=
≠if
ifIf we use more common n+ 1 and n− 1 instead of Sn() and Pn(), we can see that
add ,()ab =−add 1()ab, 1+.
This translates neatly in Python, as shown in the following command snippet:
def add(a,b):
if a == 0: return b
else: return add(a-1, b+1)
We've simply rearranged common mathematical notation into Python. The if
clauses are placed to the left instead of the right.
Generally, we don't provide our own functions in Python to do simple addition.
We rely on Python's underlying implementation to properly handle arithmetic
of various kinds. Our point here is that fundamental scalar arithmetic can be
defined recursively.
All of these recursive definitions include at least two cases: the nonrecursive cases
where the value of the function is defined directly and recursive cases where the
value of the function is computed from a recursive evaluation of the function with
different values.
In order to be sure the recursion will terminate, it's important to see how the
recursive case computes values that approach the defined nonrecursive case. There
are often constraints on the argument values that we've omitted from the functions
here. The add() function in the preceding command snippet, for example, can
include assert a>= and b>=0 to establish the constraints on the input values.