6.1 Simple numerical recursions

We can consider all numeric operations to be defined by recursions. For more details, read about the Peano axioms that define the essential features of numbers at https://www.britannica.com/science/Peano-axioms.

From these axioms, we can see that addition is defined recursively using more primitive notions of the next number, or the successor of a number n, S(n).

To simplify the presentation, we’ll assume that we can define a predecessor function, P(n), such that n = S(P(n)) = P(S(n)), as long as n≠0. This formalizes the idea that a number is the successor of the number’s predecessor.

Addition between two natural numbers could be defined recursively as follows:

If we use the more typical notations of n + 1 and n− 1 instead of S(n) and P(n), we can more easily see how the rule add(a,b) = add(a − 1,b + 1) when a≠0 works.

This translates neatly into Python, as shown in the following function definition:

def add...