SUNY Geneseo Department of Computer Science

Recurrence Relations and Recursive Algorithms

Previous Lecture

Misc

First hour exam Thursday (Oct. 7)

• Sample Exam on Web
• 3 - 5 short-answer questions
• Covers all material to that point (e.g., object oriented algorithms, experimentation, recursion, induction, recurrences)
• Whole class period
• Open book, notes, computers
  • Closed person

I'm out of town (most of) Wednesday through Sunday after Fall break (i.e., gone Oct. 13 through 17).

• Class Thursday, Oct. 14 will be Career Services presentation re what they do, geared to CS people.

Questions?

Reading Summary

Rest of Section 7.2 (i.e., middle of page 230 through middle of page 238)

When number of steps not equal to parameter

• e.g., robot moving to wall
• Can still derive recurrence relation to quantity that measures problem size
• Use "if ( okToMove..." as a step

Recurrences make it easier to analyze number of steps in complex recursions

• e.g., actions before and after recursive message

As abstract summaries of algorithm, same recurrence may arise from several algorithms, only solve it once

Count steps to represent execution time

• Closed form of recurrence is proportional to time

Count Occurrences of a Character in a String

    count( char c, String s )
        if ( s.length() == 0 )
            return 0
        else if ( s.charAt(0) == c )
            return 1 + count( c, s.substring(1) )
        else
            return count( c, s.substring(1) )

How many string operations does this do to count characters in an n-character string?

Set up recurrence

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

Find closed form

• f(n) = 3n + 1 ?
• From pattern hunting:

• Prove f(n) = 3n + 1 by induction on n
  • Base case, n = 0
    • f(n) = 1 (from first line of recurrence)
    • = 3 * 0 + 1
  • Assume f(k-1) = 3(k-1) + 1, k-1 >= 0
  • Show f(k) = 3k + 1, k >= 1
    • f(k) = 3 + f(k-1) (from recurence, 2nd line)
    • = 3 + 3(k-1) + 1 (from induction)
    • = 3 + 3k-3 + 1
    • = 3k + 1

Does a String Contain a Capital Letter

    hasCapital( str )
        if ( str.length() == 0 )
            return false
        else if ( str.charAt(0) is upper case )
            return true
        else
            return hasCapital( str.substring(1) )

What is the worst-case number of string operations this does to check an n-character string?

Worst case is when no capital letters

Recurrence relation

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

Closed form:

• f(n) = 3n + 1
• We just did this!

Towers of Hanoi

    solve( n, source, spare, dest )
        if n > 0
            solve( n-1, source, dest, spare )
            move_disk( source, dest )
            solve( n-1, spare, source, dest )

How many "move_disk" operations does this do to move an n-disk tower?

• guess 2(n-1) + 1?
• 2ⁿ ?

Recurrence relation:

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

Closed form (from the reading)

Next

(Oct. 14: career services)

Oct. 19: Relating step counts to execution time

• Read Section 9.2

Next Lecture