Recursion Formula- Definition and Examples

What Is a Recursion Formula?

A recursion formula defines a sequence by expressing each term based on previous terms. You start with one or more base cases, then use the formula to build every subsequent term.

That's it. No magic. Just a definition that feeds on itself.

Instead of giving you a direct formula like a_n = 2n + 1, a recursive formula tells you: "to get the next term, take the previous term and do this to it."

The Two Parts You Must Have

Every recursive formula needs exactly two things:

• Base case(s): The starting value(s) that anchor the sequence. Without this, you have nothing to build from.
• Recursive step: The rule that tells you how to calculate any term from the terms before it.

Miss either part, and your recursion doesn't work. Period.

Classic Examples

Factorial

The factorial is the most straightforward example. It's used everywhere in combinatorics and probability.

Definition:

• Base case: 0! = 1
• Recursive step: n! = n × (n-1)!

So 5! = 5 × 4! = 5 × 4 × 3! = 5 × 4 × 3 × 2 × 1 = 120.

Fibonacci Sequence

Fibonacci shows up in nature, computer science, and way too many "patterns in the universe" YouTube videos. Here's the actual formula:

• Base cases: F(0) = 0, F(1) = 1
• Recursive step: F(n) = F(n-1) + F(n-2)

The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Each number is just the sum of the two before it. Nothing mystical about it.

Arithmetic Sequence

Even boring linear sequences can be written recursively:

• Base case: a(1) = 3
• Recursive step: a(n) = a(n-1) + 5

This generates: 3, 8, 13, 18, 23...

The explicit formula would be a(n) = 5n - 2. Both work. The recursive version just makes you do more steps to find a specific term.

Geometric Sequence

For exponential growth or decay:

• Base case: g(0) = 2
• Recursive step: g(n) = 3 × g(n-1)

This gives: 2, 6, 18, 54, 162...

Recursion vs. Iteration: When to Use Which

You can always rewrite a recursive formula as an iterative loop. Sometimes you should. Sometimes you shouldn't.

For Fibonacci, the naive recursive approach calculates the same values exponentially many times. That's a disaster. Use iteration or memoization instead.

How to Write a Recursion Formula (Getting Started)

Here's the process when someone gives you a sequence and asks for a recursive formula:

Step 1: Find the Pattern

Look at how each term relates to the previous ones. Is there a constant difference? A constant ratio? A combination of previous terms?

Step 2: Identify the Base Case

What value(s) can you determine without any previous terms? Usually the first one or two terms.

Step 3: Write the Recursive Step

Express a(n) in terms of a(n-1), a(n-2), etc. The step should work for any n greater than your base case index.

Step 4: Test It

Calculate the first few terms using your formula. Do they match the original sequence? If not, go back to step 1.

Example: Given the sequence 5, 9, 13, 17, 21...

• Difference is 4 each time
• Base case: a(1) = 5
• Recursive step: a(n) = a(n-1) + 4

Test: a(2) = a(1) + 4 = 5 + 4 = 9 ✓

Common Mistakes

• Forgetting the base case: Your formula has nothing to start from.
• Wrong index: Writing a(n) = a(n) + 3 creates a circular definition that solves for nothing.
• Assuming too much: Not every sequence has a simple recursive form. Some patterns are just random numbers.
• Stack overflow: In programming, deep recursion without optimization crashes your program.

When Recursion Actually Makes Sense

Recursive formulas aren't just mathematical exercises. They model real situations:

• Compound interest: Balance depends on previous balance
• Population growth: Next year's population depends on this year's
• Algorithm design: Divide-and-conquer strategies often use recursive structure
• File systems: Folder size depends on contents, which may contain subfolders

If the problem naturally breaks into "same problem, smaller input," recursion fits.