6. From Recursion to Induction and Algorithms

So far, recursion tables have been used to define functions. But the same structure also supports reasoning and computation more generally.

When we define a function by recursion, we proceed by cases that follow the way values are built. This is closely related to how proofs by induction work.

To prove a property for all natural numbers, we typically do two things:

• show it holds for $zero$
• show that if it holds for $k$, it also holds for $suc(k)$

This mirrors the structure of the constructors. What is built in one step is handled in one step.

Recursion tables make this correspondence visible. Each row of the table corresponds to a case that must be handled. The recursive entries correspond to the step where we reduce a problem to a simpler one.

This can be used to reason about functions directly.

Consider the claim:

If $a * b = zero$, then $a = zero$ or $b = zero$.

Looking at the recursion table for multiplication, we see immediately:

• whenever one of the arguments is $zero$, the result is $zero$
• whenever both arguments are of the form $suc(...)$, the result is built using addition of a successor

In particular, in the recursive case the result cannot be $zero$, because it contains at least one $suc$. So the only way to obtain $zero$ is through the base cases.

The argument is convincing without a separate formal proof. The conviction arises from inspecting how the function is defined.

This correspondence is not only structural. It can be used directly.

Consider the claim:

$$ n + zero = n $$

Looking at the recursion table for addition, we see:

• in the row for $zero$ and the column for $zero$, the result is $zero$, so the claim holds
• in the row for $suc(k)$ and the column for $zero$, the result is $suc(k)$, so the claim also holds

Every possible case of $n$ appears in the table. No further argument is needed. The table itself already shows that the property holds for all natural numbers.

The same idea appears in programming.

Recursive algorithms are often defined on data types that are built from a small number of constructors. Lists, for example, are either empty or built by adding an element to a smaller list. If that is the case, recursion tables can be used to define a function.

A function like the length of a list follows this structure:

Each step removes one element from the list. The algorithm terminates because there are only finitely many elements to remove.

What becomes apparent across these examples is a general pattern.

• data is built in a finite number of steps
• functions follow that structure
• reasoning follows it as well

Recursion tables bring these three aspects together in one place.

They do not replace formal reasoning. But they make it possible to be convinced that proofs and programs work in an intuitive way before following proofs.

This is another situation in which conviction forms through visibility: not by checking each step in isolation, but by seeing how the whole process is structured.