Recursion and Recursive Sequences

What is Recursion?

Recursion: Defining something in terms of itself

Recursive sequence: Each term defined using previous term(s)

Components:

1. Base case: Starting value(s)
2. Recursive rule: How to get next term from previous

Like: Following directions that reference themselves

Recursive vs Explicit Formulas

Explicit formula: Direct calculation of any term

• Example: aₙ = 2n + 1

Recursive formula: Calculate term from previous

• Example: a₁ = 3, aₙ = aₙ₋₁ + 2

Trade-off:

• Explicit: Fast for any term
• Recursive: May be simpler to write

Example: Compare Formulas

Sequence: 5, 8, 11, 14, 17...

Explicit: aₙ = 3n + 2

Recursive:

a₁ = 5
aₙ = aₙ₋₁ + 3

Find a₁₀:

• Explicit: a₁₀ = 3(10) + 2 = 32 ✓ Fast!
• Recursive: Must calculate a₂, a₃, ... a₉ first

Writing Recursive Formulas

Steps:

1. Identify first term (base case)
2. Find pattern relating consecutive terms
3. Write recursive rule

Example 1: Arithmetic Sequence

Sequence: 4, 7, 10, 13...

Base case: a₁ = 4

Pattern: Each term is 3 more than previous

Recursive formula:

a₁ = 4
aₙ = aₙ₋₁ + 3

Example 2: Geometric Sequence

Sequence: 3, 6, 12, 24...

Base case: a₁ = 3

Pattern: Each term is 2 times previous

Recursive formula:

a₁ = 3
aₙ = 2·aₙ₋₁

Fibonacci Sequence

Most famous recursive sequence

Rule: Each term is sum of previous two

Formula:

F₁ = 1
F₂ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂ (for n ≥ 3)

Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Example: Calculate Fibonacci Terms

F₃ = F₂ + F₁ = 1 + 1 = 2

F₄ = F₃ + F₂ = 2 + 1 = 3

F₅ = F₄ + F₃ = 3 + 2 = 5

F₆ = F₅ + F₄ = 5 + 3 = 8

F₇ = F₆ + F₅ = 8 + 5 = 13

Fibonacci in Nature

Golden spiral: Shell patterns follow Fibonacci

Flower petals: Often Fibonacci numbers (3, 5, 8, 13...)

Tree branches: Branching patterns follow Fibonacci

Pinecones: Spirals count Fibonacci numbers

Human body: Proportions approximate golden ratio

Example: Flower Petals

Lilies: 3 petals Buttercups: 5 petals Delphiniums: 8 petals Marigolds: 13 petals Daisies: 21 or 34 petals

All Fibonacci numbers!

Golden Ratio

As Fibonacci numbers grow, ratio approaches φ (phi)

φ = (1 + √5)/2 ≈ 1.618...

Ratios:

F₂/F₁ = 1/1 = 1
F₃/F₂ = 2/1 = 2
F₄/F₃ = 3/2 = 1.5
F₅/F₄ = 5/3 ≈ 1.667
F₆/F₅ = 8/5 = 1.6
F₇/F₆ = 13/8 = 1.625
F₈/F₇ = 21/13 ≈ 1.615

Approaching 1.618...

Two-Term Recursion

General form: aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂

Need two base cases

Example 1: Custom Sequence

Define:

a₁ = 2
a₂ = 5
aₙ = aₙ₋₁ + 2·aₙ₋₂

Calculate:

a₃ = a₂ + 2·a₁ = 5 + 2(2) = 9
a₄ = a₃ + 2·a₂ = 9 + 2(5) = 19
a₅ = a₄ + 2·a₃ = 19 + 2(9) = 37

Sequence: 2, 5, 9, 19, 37...

Example 2: Lucas Numbers

Similar to Fibonacci, different start:

L₁ = 2
L₂ = 1
Lₙ = Lₙ₋₁ + Lₙ₋₂

Sequence: 2, 1, 3, 4, 7, 11, 18, 29...

Factorial Recursion

Factorial: n! = n × (n-1) × ... × 2 × 1

Recursive definition:

0! = 1 (base case)
n! = n × (n-1)!

Example: Calculate Factorials

3! = 3 × 2! = 3 × 2 = 6

4! = 4 × 3! = 4 × 6 = 24

5! = 5 × 4! = 5 × 24 = 120

Recursive process:

5! = 5 × 4!
   = 5 × (4 × 3!)
   = 5 × 4 × (3 × 2!)
   = 5 × 4 × 3 × (2 × 1!)
   = 5 × 4 × 3 × 2 × 1
   = 120

Tower of Hanoi

Classic recursion problem

Rules:

• Move n disks from pole A to pole C
• Use pole B as auxiliary
• Never place larger disk on smaller

Minimum moves:

H₁ = 1 (one disk: just move it)
Hₙ = 2·Hₙ₋₁ + 1

Example: Tower Moves

H₁ = 1 (1 disk: 1 move)

H₂ = 2(1) + 1 = 3 (2 disks: 3 moves)

H₃ = 2(3) + 1 = 7 (3 disks: 7 moves)

H₄ = 2(7) + 1 = 15 (4 disks: 15 moves)

Pattern: Hₙ = 2ⁿ - 1

Compound Interest Recursion

Recursive model for savings

Formula:

A₀ = P (initial deposit)
Aₙ = r·Aₙ₋₁ + d

Where:

• r = growth factor (1 + interest rate)
• d = regular deposit

Example: Savings Account

Start: $1000 Interest: 5% per year (r = 1.05) Annual deposit: $500

Year 0: A₀ = $1000

Year 1: A₁ = 1.05(1000) + 500 = $1550

Year 2: A₂ = 1.05(1550) + 500 = $2127.50

Year 3: A₃ = 1.05(2127.50) + 500 = $2733.88

Population Growth

Model population with recursion

Simple model:

P₀ = initial population
Pₙ = r·Pₙ₋₁

With carrying capacity:

Pₙ = Pₙ₋₁ + r·Pₙ₋₁(1 - Pₙ₋₁/K)

Where K = carrying capacity (maximum sustainable)

Example: Bacteria Growth

Start: P₀ = 100 bacteria Growth rate: 50% per hour (r = 1.5)

P₁ = 1.5 × 100 = 150

P₂ = 1.5 × 150 = 225

P₃ = 1.5 × 225 ≈ 338

P₄ = 1.5 × 338 ≈ 506

Collatz Conjecture

Unsolved problem in mathematics

Rule:

Start with any positive integer n
If n is even: divide by 2
If n is odd: multiply by 3 and add 1
Repeat until reaching 1

Conjecture: Always reaches 1 (unproven!)

Example: Collatz Sequence

Start with 7:

7 (odd) → 3(7)+1 = 22
22 (even) → 22/2 = 11
11 (odd) → 3(11)+1 = 34
34 (even) → 34/2 = 17
17 (odd) → 3(17)+1 = 52
52 (even) → 52/2 = 26
26 (even) → 26/2 = 13
13 (odd) → 3(13)+1 = 40
40 (even) → 40/2 = 20
20 (even) → 20/2 = 10
10 (even) → 10/2 = 5
5 (odd) → 3(5)+1 = 16
16 (even) → 16/2 = 8
8 (even) → 8/2 = 4
4 (even) → 4/2 = 2
2 (even) → 2/2 = 1 ✓

Reached 1 after 16 steps

Converting Recursive to Explicit

Sometimes possible to find explicit formula

For linear recursion aₙ = c·aₙ₋₁ + d:

If d = 0: aₙ = a₁·cⁿ⁻¹ (geometric)

If c = 1: aₙ = a₁ + (n-1)d (arithmetic)

Example: Find Explicit Formula

Recursive:

a₁ = 3
aₙ = 2·aₙ₋₁

This is geometric with r = 2

Explicit: aₙ = 3 × 2ⁿ⁻¹

Check:

• a₁ = 3 × 2⁰ = 3 ✓
• a₂ = 3 × 2¹ = 6 ✓
• a₃ = 3 × 2² = 12 ✓

Recursion in Programming

Recursion is fundamental in computer science

Function calls itself

Must have base case to stop

Example: Factorial Code (Pseudocode)

function factorial(n):
    if n == 0:
        return 1       // base case
    else:
        return n × factorial(n-1)  // recursive call

Practice