Course contentsShow
← Computer Science
Lesson 84 of 2,8722. Discrete Mathematics for CSFree lesson

Recurrence Relations

Defining sequences recursively where terms depend on previous terms, forming the basis for recursive thinking.

Recurrence Relations

You'll learn how to define sequences where each term is calculated using earlier terms—a pattern that underlies recursion in programming.

What Is a Recurrence Relation?

A recurrence relation is a formula that defines each term of a sequence based on one or more previous terms. Instead of writing out every value, you specify:

  1. A rule connecting terms (the recurrence itself)
  2. Initial values to start the sequence

Think of it like a chain reaction: you know the first domino's position, and each subsequent domino's position depends on where the previous ones fell.

Example: The Fibonacci Sequence

The famous Fibonacci sequence is defined by:

  • Rule: a(n) = a(n-1) + a(n-2) (each term is the sum of the two before it)
  • Initial values: a(0) = 0, a(1) = 1

This generates: 0, 1, 1, 2, 3, 5, 8, 13...

Notice we didn't calculate the 100th term directly—we expressed how to build it from earlier terms.

Why This Matters in CS

Recurrence relations model:

  • Recursive algorithms (e.g., computing factorials, tree traversals)
  • Algorithm complexity (analyzing how runtime grows)
  • Dynamic programming problems

Instead of thinking "what's the final answer?", you think "how does each step depend on what came before?" This shift in perspective is the foundation of recursive thinking.

Anatomy of a Recurrence

  1. Base case(s): Starting values that don't depend on others
  2. Recursive case: Formula using previous term(s)

Without base cases, the relation is undefined—like trying to climb a ladder with no bottom rung!

Key Takeaway: A recurrence relation defines a sequence by expressing each term as a function of previous terms, paired with initial conditions—this recursive structure mirrors how many algorithms break problems into smaller subproblems.