Mathematics.

sequences and recursion

Recursive Definitions

Discrete Mathematics25 minDifficulty4 out of 10

You should know: mathematical induction

Overview

A recursive definition defines an object — a function, a sequence, or a set — in terms of smaller or simpler instances of itself, together with one or more base cases that stop the self-reference from going on forever. Every recursive definition has exactly two parts: base case(s) that state the value(s) directly for the smallest inputs, and a recursive (inductive) step that builds the value for a larger input out of values for smaller ones. This structure is the definitional twin of mathematical induction: a base case anchors the definition, and a recursive step lets every larger case be reduced, step by step, back down to that anchor. Recursive definitions describe factorials, Fibonacci numbers, the natural numbers themselves (via the Peano axioms), and recursively defined sets like the set of well-formed arithmetic expressions.

Intuition

A recursive definition is like a set of nesting dolls with a smallest, solid doll at the center: to open (evaluate) any doll, the rule says 'open the doll just inside you and use what's there' — except for the innermost doll, which is simply handed to you already assembled (the base case). Evaluating f(5) triggers a chain f(5) depends on f(4), which depends on f(3), and so on, unwinding down to f(0), which is known outright; then the answers wind back up the chain, each level combining its own input with the answer from the level below. Without the base case this chain would never bottom out — which is exactly why every valid recursive definition needs one.

Formal Definition

Definition

A recursive definition of a function f on the natural numbers consists of a base case fixing f at the smallest input, and a recursive step expressing f(n) in terms of f at strictly smaller inputs:

f(0)=c(base case)f(0) = c \quad \text{(base case)}
Base case
f(n)=g(n,f(n−1))for n≥1(recursive step)f(n) = g\big(n, f(n-1)\big) \quad \text{for } n \ge 1 \quad \text{(recursive step)}
Recursive step
0!=1,n!=n⋅(n−1)! for n≥10! = 1, \qquad n! = n \cdot (n-1)! \text{ for } n \ge 1
Factorial, recursively defined
F0=0, F1=1,Fn=Fn−1+Fn−2 for n≥2F_0 = 0,\ F_1 = 1, \qquad F_n = F_{n-1} + F_{n-2} \text{ for } n \ge 2
Fibonacci sequence, recursively defined

Worked Examples

  1. Unwind the recursion down to the base case.

    4!=4⋅3!,3!=3⋅2!,2!=2⋅1!,1!=1⋅0!4! = 4\cdot 3!,\quad 3! = 3\cdot 2!,\quad 2! = 2\cdot 1!,\quad 1! = 1\cdot 0!

  2. The base case gives 0! = 1; wind back up.

    1!=1⋅1=1,2!=2⋅1=2,3!=3⋅2=6,4!=4⋅6=241! = 1\cdot 1 = 1,\quad 2! = 2\cdot 1 = 2,\quad 3! = 3\cdot 2 = 6,\quad 4! = 4\cdot 6 = 24

Answer: 4! = 24.

Practice Problems

Difficulty 3/10

Using F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂, compute F₆.

Difficulty 4/10

A sequence is defined by b(0) = 2 and b(n) = b(n-1)² - 1 for n ≥ 1. Compute b(2).

Difficulty 5/10

A savings account starts with $100 (month 0) and each month's balance is defined recursively as balance(n) = balance(n-1) + 0.10·balance(n-1) = 1.10·balance(n-1) (10% monthly growth, compounded). What is the balance after 3 months?

Quiz

Every valid recursive definition must include:
In the recursive definition 0! = 1, n! = n·(n-1)!, evaluating 3! requires:
Recursive definitions are the definitional counterpart of which proof technique?

Summary

  • A recursive definition has a base case (stated directly) and a recursive step (built from smaller instances).
  • Evaluating a recursively defined object unwinds to the base case, then combines results back up the chain.
  • Factorial (0!=1, n!=n·(n-1)!) and Fibonacci (F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂) are the canonical examples.
  • Recursive definitions are the definitional mirror of mathematical induction: base case anchors, recursive step propagates.

References

  1. WebsiteWikipedia — Recursive definition