Mathwords logoReference LibraryMathwords

Recursion

Recursion is a way of defining a sequence or function where each value is calculated using one or more previous values. You start with a known base case and then apply a rule repeatedly to generate new terms.

A recursive definition consists of two parts: one or more base cases that provide explicit starting values, and a recursive rule (or recurrence relation) that expresses each subsequent term as a function of preceding terms. Formally, a sequence {an}\{a_n\} is defined recursively if an=f(an−1,an−2,…)a_n = f(a_{n-1}, a_{n-2}, \ldots) for nn greater than some initial index, together with specified values for the initial terms. Recursion also applies to functions that call themselves, a concept central to computer science and algorithm design.

Key Formula

an=f(an−1,an−2,…),with base case(s) givena_n = f(a_{n-1}, a_{n-2}, \ldots), \quad \text{with base case(s) given}
Where:
  • ana_n = the term at position n in the sequence
  • ff = a rule that combines one or more previous terms to produce the next term
  • an−1,an−2,…a_{n-1}, a_{n-2}, \ldots = the preceding terms that the current term depends on

Worked Example

Problem: A sequence is defined recursively by a₁ = 3 and aₙ = 2aₙ₋₁ + 1 for n ≥ 2. Find the first five terms.
Step 1: Start with the base case.
a1=3a_1 = 3
Step 2: Apply the recursive rule to find the second term.
a2=2a1+1=2(3)+1=7a_2 = 2a_1 + 1 = 2(3) + 1 = 7
Step 3: Continue applying the rule for the third term.
a3=2a2+1=2(7)+1=15a_3 = 2a_2 + 1 = 2(7) + 1 = 15
Step 4: Find the fourth and fifth terms the same way.
a4=2(15)+1=31,a5=2(31)+1=63a_4 = 2(15) + 1 = 31, \quad a_5 = 2(31) + 1 = 63
Answer: The first five terms are 3, 7, 15, 31, 63.

Visualization

Why It Matters

Recursion is foundational in both mathematics and computer science. Algorithms for sorting, searching, and traversing data structures often use recursive logic. In mathematics, many important sequences — including the Fibonacci numbers and factorials — are most naturally described using recursive definitions.

Common Mistakes

Mistake: Forgetting the base case and trying to apply the recursive rule endlessly.
Correction: Every recursive definition needs at least one base case. Without it, you have no starting point and the sequence or function is undefined.
Mistake: Confusing a recursive formula with an explicit (closed-form) formula.
Correction: A recursive formula tells you how to get the next term from previous terms. An explicit formula lets you calculate any term directly from its position number n, without computing all the terms before it.

Related Terms