Python simple numerical recursion

Python Simple Numerical Recursion. All numerical computations can be defined recursively. For more information on the Peano axioms, visit Wikipedia.

From these axioms, it’s easy to see that addition is recursively defined using a more fundamental concept: the next number (also called the “successor”) S(n) of a number n.

For ease of understanding, first define the prefix function P(n). When ndoes not equal 0, this function satisfies n = S(P(n)) = P(S(n)).

This allows us to recursively define the addition of two natural numbers, as follows:

If we replace S(n) and P(n) with the more common n+1 and n-1, then add(a,b) = add(a-1,b+1).

The above formula can be converted into Python code as follows:

def add(a: int, b: int) -> int:
if a == 0:
return b
else:
return add(a - 1, b + 1)

This is just a re-arrangement of the mathematical symbols to fit Python syntax.

In fact, there’s no need to write a function in Python to implement addition; Python’s existing functionality is sufficient to implement various arithmetic operations. This example illustrates that basic scalar calculations can be defined recursively, and their implementation is straightforward.

A recursive definition includes at least two cases: the non-recursive case (also called the “base case”), which directly returns a fixed value; and the recursive case, where the function returns a value by calling itself with different input parameters.

To ensure that the recursion terminates, it’s important to understand how the input value approaches the non-recursive parameter. Although not specified in the previously defined functions, input parameters often have conditional constraints. For example, in the previously defined add() function, the input value constraints are: assert a >= 0 and b >= 0.

Without these constraints, there’s no guarantee that the function will approach a == 0 when a is -1.