Demonstrating Recursion, Factorials, and Iteration in Mathematics

1. Recursive Definitions on ℕ

Mathematics often defines functions on the natural numbers by:

1. A base case at 0 (or 1).
2. A step rule that reduces the argument to a “simpler” one.

1.1 Addition (Peano-style)

• Base: a + 0 = a
• Step: a + S(b) = S(a + b) (Here S(b) means “the successor of b”, i.e. b + 1.)

1.2 Multiplication

• Base: a × 0 = 0
• Step: a × S(b) = (a × b) + a

1.3 Factorial

• Base: 0! = 1
• Step: n! = n × (n − 1)!

2. From Recursion to Iteration

2.1 Recursive Pseudocode

function fact(n):
  if n == 0:
    return 1
  else:
    return n * fact(n-1)

2.2 Iterative Pseudocode

function fact(n):
  product ← 1
  for i from 1 to n:
    product ← product * i
  return product

3. Other Classic Examples

3.1 Fibonacci Sequence

• Recursive: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
• Iterative: Maintain two running values and loop up to n.

3.2 Summation & Product Notation

• Summation: ∑_i=1ⁿ i is an iterative shorthand for adding.
• Recursive: S(0) = 0, S(n) = n + S(n-1).

4. Why Recursion & Iteration Are Fundamental

• Inductive Structure of ℕ: Natural numbers are built by zero plus repeated successors. Recursive definitions mirror this.
• Expressiveness: Many mathematical objects (trees, sequences) are inherently recursive; definitions are more concise.
• Algorithmic Equivalence: By the Church–Turing thesis, any computable function has both recursive and iterative forms.
• Proof Techniques: Induction over a recursive definition is straightforward—verify base and step cases.
• Efficiency vs. Clarity: Recursion aligns with definitions; iteration often yields better performance in practice.

In Summary

• Recursive definitions use a base case plus a step rule over ℕ.
• Iteration “unrolls” recursion into loops for efficient computation.
• The interplay of recursion and iteration underpins arithmetic, combinatorics, and computation.