SUNY Geneseo Department of Computer Science

Introduction to Recurrence Relations

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Voter registration

Lab handout will be available in labs tomorrow

Exam 1 is this Friday (Oct. 10)

Basics of design, theory, experimentation, and recursion, induction, recurrences
Open book, open notes, open computer
3 - 5 short-answer questions (algorithms, proofs, paragraphs, etc.)
Whole class period
Sample Test will be on Web

Questions?

Recurrence Relations

Section 7.2.1

Recurrence relation is recursive definition of math function

Analysis of recurrence relations involves telling how many recursive steps it does

Proof for V(m):

V(m) = 1.005^m
= 1.005 V(m-1)

Closed form = non-recursive expression that defines same function as recurrence relation

Closed forms can often be derived from recurrence

Example

Find a closed form for

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

n	f(n)
0	2
1	5 + f(0) = 5 + 2 = 7
2	5 + f(1) = 5 + (5+2) = 12
3	5 + (5+5+2) = 17
4	5 + (5+5+5+2) = 22

Closed form: f(n) = 5n + 2 ?

Prove this guess (f(n) = 5n + 2) right by induction on n

Base case: n = 0
- f(0) = 2 [first line of definition]
- = 5 * 0 + 2
Induction step
- Assume k-1 is natural number, f(k-1) = 5(k-1) + 2
- Show f(k) = 5k + 2
  - f(k) = 5 + f(k-1) [ definition ]
  - = 5 + 5(k-1) + 2
  - = 5 +5k - 5 + 2
  - = 5k + 2

Application to Algorithms

e.g., how many robot messages (move, turns, paint, etc.) in

    walk( n )
        if ( n > 0 )
            this.move()
            this.walk( n - 1 )
        else
            this.turnLeft()
            this.turnLeft()

f(n) is number of robot messages that "walk" sends when given parameter n

Recurrence relation

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

Read Section 7.2.2 through factorial example (pg. 297)

Mini-assignment: How many "println" messages in

    countDown( n )
        if ( n > 1 )
            System.out.println( n )
            countDown( n - 1 )

Next Lecture