5. More Examples: Addition and Multiplication

Once the pattern is clear, other functions on the natural numbers follow the same structure.

Consider addition. We want a function that constructs the sum of two numbers.

The corresponding recursion table has the same shape as before:

The table can be read directly.

• If the first argument is $zero$, the result is the second argument
• If the second argument is $zero$, the result is the first argument
• If both are $zero$, the result is $zero$.
• If both are successors, we reduce the first argument and keep track of the step with an additional $suc$

Each recursive step removes one layer from the first argument. The computation ends when that argument becomes $zero$.

Let's look at 2 + 2:

2 + 2 = $suc(suc(zero)) + suc(suc(zero))$

$= suc(suc(zero) + suc(suc(zero)))$

$= suc(suc(zero + suc(suc(zero))))$

$= suc(suc(suc(suc(zero)))) = 4$

Multiplication follows the same idea, but builds on addition:

Again, the table shows everything.

• If either argument is $zero$, the result is $zero$
• Otherwise, the problem is reduced step by step
• Each step replaces multiplication by a smaller multiplication plus an addition

What changes from example to example is not the structure of the table, but what happens in the recursive case.

This is the main pattern:

• base cases give direct values
• recursive cases reduce the problem
• the table shows both at once

Once this is understood, new functions can be constructed in the same way. The table provides a template: list all constructor combinations, fill in the base cases, and define the recursive ones so that they move toward them.