SUNY Geneseo Department of Computer Science

Introduction to Recurrence Relations

Previous Lecture

Misc

Next week I'm out of town Wednesday through Friday, Prof. Zollo gives lectures

Questions?

Recurrence Relations

Section 7.2.1

Recurrence relations

• Multi-part function definitions, each part has conditions under which it applies
• At least one part involves recursion
• At least one part isn't recursive
• Used to analyze number of steps a recursive algorithm executes

Induction to prove recurrence relations

• Specifically, to prove equivalence of recurrence and closed form

Closed forms = non-recursive expressions that produce same value as a recurrence

Examples

Introductory example

• The recurrence
  • f(n) = 2 if n = 0
  • f(n) = 5 + f(n-1) if n > 0
• Try evaluating it
  • f(2) = 5 + f(1)
  • = 5 + ( 5 + f(0) )
  • = 5 + ( 5 + 2 )
  • = 12
• Closed form?
  • Pattern

• Hmm: f(n) = 5n + 2 ?
• Prove that f(n) as defined by recurrence = 5n + 2
  • By induction on n
  • Base case, n = 0. f(n) from recurrence = 2 = 5*0 + 2
  • Induction hypothesis: f(k-1) = 5(k-1) + 2, k-1 >= 0
  • Show f(k) = 5k + 2
    • k > 0, so
    • f(k) = 5 + f(k-1) from recurrence
    • = 5 + 5(k-1) + 2 from induction hyp
    • = 5 + 5k - 5 + 2
    • = 5k + 2

Another...

• Recurrence
  • f(n) = 7 if n = 0
  • f(n) = 1 + f(n-1) if n > 0
• f(n) = n + 7?
  • By analogy to first example
• Prove by induction on n
  • Base case, n = 0
    • f(0) = 7 = 0 + 7 = n + 7
  • Induction hypothesis, f(k-1) = k-1 + 7
  • Show f(k) = k + 7
    • f(k) = 1 + f(k-1)
    • = 1 + k-1 + 7
    • = k + 7
• Illustrates a general pattern, recurrences of the form f(0) = c; f(n>0) = k + f(n-1) always have closed forms of the form f(n) = kn + c. See Exercise 7.15.1

Connection to Algorithms

How many primitive Robot messages does this send while painting an n-tile line?

• Assume precondition n >= 1

    // In some subclass of Robot...
    paintLine( n )
        if n > 1
            this.paint( red )
            this.move()
            this.paintLine( n-1 )
        else
            this.paint( red )

Let p(n) = number of primitive messages sent, as function of n

• p(n) = 1 if n = 1
• p(n) = p(n-1) + 2 if n > 1

Read Section 7.2.2

Next Lecture