SUNY Geneseo Department of Computer Science

Induction and Recursion, Part 2

Previous Lecture

Misc

I'm out of town Friday (Oct. 3)

• Class will be a guest presentation by Career Services re where you might go with a CS major/minor/etc

Hand out Homework 1

Questions?

halfWayBack algorithm

• Walk to wall and twice as far back

    if okToMove()
        move()
        wallAndBack()
        move()
        move()
    else
        turn around

Induction Examples

Prove that this algorithm determines whether natural number n is odd or even:

    isOdd( n )
        if ( n == 0 )
            return false
        else if ( n == 1 )
            return true
        else 
            return isOdd( n - 2 )

Mini-assignment

One base case or two?

• Maybe 2
• Base case 1: n = 0
  • 0 is no odd, false should be returned and is
• Base case 2: n = 1
  • 1 is odd, so first test fails, second passes, returns true, which is correct since n is odd

Induction? Works for k-1 >= 1?

• How about k-2?
• Induction hypothesis: assume k-2 >= 0 and isOdd(k-2) returns true if k-2 is odd and false if k-2 is even
• Show that isOdd(k) returns true if k is odd and false if k is even.
  • k >= 2 since k-2 >= 0
  • So isOdd executes the 3rd arm of of conditional, and returns isOdd(k-2)
  • From induction hyp., isOdd(k-2) correctly classifies k-2 as odd/even
  • k is odd/even exactly as k-2 is
  • So isOdd(k-2) should be what isOdd(k) returns, which it is

Next

Techniques for counting operations in recursive algorithms

Read Section 7.2.1

Next Lecture