SUNY Geneseo Department of Computer Science

Introduction to Recurrence Relations

Previous Lecture

Misc

Hand out Lab 6

Lab 4 Solution is on the Web

Questions?

Recurrence Relations

Key tool for performance analysis of recursive algorithms

Section 7.2.1

Recurrence relations and math

Interest example

• Algorithm or formula

Non-recursive version

• Involved exponentiation

Prove equivalence inductively

Closed forms

• Changing recursive version to nonrecursive one

Example Recurrence

Find closed form for

• f(n) = 3 if n = 0
• f(n) = 1 + f(n-1) if n > 0

What is f(3)?

• f(3) = 1 + f(2)
• = 1 + 1 + f(1)
• = 1 + 1 + 1 + f(0)
• = 1 + 1 + 1 + 3
• = 6

Closed form

• f(n) = n+3 ?
• Pattern in expansion of f(3) suggests 1 one for each unit in n, plus 3 at end

Prove this

• Just like any other induction
• Base case, n = 0.
  • Closed form f(0) = 0 + 3 = 3
  • Recurrence relation, f(0) = 3
• Assume f(k-1) = (k-1) + 3 = k+2
• Consider f(k)
  • f(k) = 1 + f(k-1) from recurrence
  • = 1 + k + 2 induction hypothesis
  • = k + 3
  • f(k) = k + 3 from closed form

Application to Algorithms

We started to see how the number of operations a recursive algorithm does can be "counted" by a recurrence relation -- finish it now.

For example, just how many disk moves does the towers of Hanoi algorithm require?

    solve( n, source, dest, spare )
        if n > 0
            this.solve( n-1, source, spare, dest )
            this.move( source, dest )
            this.solve( n-1, spare, dest, source )

M(n) is number of disk moves towers of Hanoi algorithm does to solve an n-disk puzzle

• M(n) = 2 M(n-1) + 1 if n > 0
• M(n) = 0 if n = 0

Closed form

• M(0) = 0
• M(1) = 1 = 2*M(0) + 1 = 2[0] + 1 = 1
• M(2) = 3 = 2*M(1) + 1 = 2[1] + 1 = 2 + 1
• M(3) = 2*M(2) + 1 = 2[2 + 1] + 1
  • = 4 + 2 + 1
  • = 2² + 2¹ + 2⁰
• M(4) = 2*M(3) + 1
  • = 2[2² + 2¹ + 2⁰] + 1

• Guess: M(n) = 2ⁿ - 1
• Prove:
  • Base case n = 0
    • M(0) = 0 from recurrence
    • = 1 - 1
    • = 2⁰ - 1
  • Induction hypothesis M(k-1) = 2^k-1 - 1
  • Show M(k) = 2^k - 1
    • M(k) = 2M(k-1) + 1 from recurrence
    • = 2[2^k-1 - 1] + 1 by induction hypothesis
    • = 2^k - 2 + 1
    • = 2^k - 1

Next

Read Section 7.2.2

Next Lecture