SUNY Geneseo Department of Computer Science

Induction and Recursion

Previous Lecture

Misc

CS Learning Center open

• 7:00 - 9:30 Sun - Thurs
• In printer room

Voter registration and information today, Sept. 28, 11:00 - 8:30, College Union

Questions?

Numbering tiles for bouncing in lab

Reading Summary

End of Section 7.1

Implicit induction - no explicit index, e.g., induction on number of steps from wall

Strong vs weak induction

• Strong: assume hypothesis for all values less than k
  • Use it when recursion works on value n that is some unknown amount smaller than in original call
• Weak: assume hypothesis for k-1

Induction to prove correctness of recursive algorithms

Proofs often prose more than equations

Search a SuperArray

Given value, x, and position, i, return True if any item between positions 0 and i of the SuperArray equals x, return False otherwise

    // In class SuperArray...
    boolean search( int x, int i )
        if i < 0
            return false
        else if A[i] == x
            return true
        else
            return this.search( x, i-1 )

Prove that this algorithm satisfies the specification above

Induction on the value of i

Base case, i = -1

• "i < 0" succeeds, so algorithm returns true
• Which is correct because there are no items between positions 0 and -1, so there can't be any = x.

Induction hypothesis, assume search returns true when x is in A between positions 0 and i = k-1 >= -1, false if x not in those positions

Show search returns true when x is in A between positions 0 and i = k

• When i = k, i >= 0 so algorithm doesn't return false right away.
• Two cases:
  • A[k] = x
    • "A[i] == x" test passes, algorithm returns true, which is what it needs to return.
  • A[k] != x

• Algorithm executes final "else"
• Recursion occurs and (by induction hypothesis) returns true if x is in positions 0 through k-1, and false otherwise
• This is the answer for all k elements, because A[k] != x, so x is in first k elements iff it's in the first k-1

Draw a Check Mark

Preconditions

• Robot is standing on outer tile of vertical stroke, facing along the stroke
• No obstacles within n tiles forward or left of robot
• n >= 1

Postconditions

• Robot is standing on outer tile of diagonal stroke, facing opposite of original direction
• Yellow checkmark has been drawn

Design algorithm

    // In some subclass of Robot
    drawCheck( int n )
        if n = 1
            this.paint( Yellow )
            turn around
        else
            this.paint( Yellow )
            this.move()
            this.drawCheck( n-1 )
            this.move()
            this.turnRight()
            this.move()
            this.paint( Yellow )
            this.turnleft()

Prove it correct

• Induction on ...
• Base case, n <= 0
  • Oops, this base case isn't quite consistent with precondition!
• New base case, n = 1

• Oops, no "paint" message!

Mini-assignment: prove final algorithm above correct (and/or fix)

Next

Analyzing the execution time of recursive algorithms

Read Section 7.2 through "A First Example" in 7.2.2 (i.e., to middle of page 230)

Next Lecture