Lesson 2: Recursive Operations

Entry conditions

Use recursive definitions only when you have a successor structure and a base element.

Definitions

Define addition and multiplication on $\mathbb{N}$ recursively:

• $n+0=n$

• $n+S(m)=S(n+m)$

• $n\cdot 0=0$

• $n\cdot S(m)=(n\cdot m)+n$

Vocabulary (plain language)

• Recursion: define a function by a base case and a step rule.
• Base case: the value at $0$.
• Step rule: how to compute at $S(m)$ using the value at $m$.

Symbols used

• $+$: addition.
• $\cdot$: multiplication.

Intuition

Arithmetic operations are not assumed; they are defined. Addition is repeated successor, and multiplication is repeated addition. These definitions make arithmetic part of the axiomatic system.

Worked example

Compute $2+1$ using recursion:

• $2+1=2+S(0)=S(2+0)=S(2)=3$.

How to recognize the structure

• You can define a function using a base case at $0$.
• You can define the step in terms of the previous value.

Common mistakes

• Using recursion without a clear base case.
• Defining an operation by intuition without a formal rule.