SUNY Geneseo Department of Computer Science

Recursion, Part 4

Previous Lecture

Misc

CS faculty/student beginning-of-year party

• Today (Friday), 3:30 - 5:30, South 322

Questions?

Drawing a Line

Design a recursive algorithm that makes a robot draw an n-tile line and then go back to its original tile.

    drawAndBack( n )
        if n > 0
            this.paint( color )
            this.move()
            this.drawAndBack( n - 1 )
            this.move()
        else
            this.turnLeft()
            this.turnLeft() 

Paul, Caitlin, and Rich were demonstrating...

Suppose postconditions were different, robot facing in original direction

    drawAndBack( n )
        if n > 0
            this.paint( color )
            this.move()
            this.drawAndBack( n - 1 )
            this.turnLeft()    // To turn robot from original direction to
            this.turnLeft()    // direction it has to move back in
            this.move()
            this.turnLeft()    // To turn robot from backwards direction to
            this.turnLeft()    // original direction, for postcondition
        else
            // do nothing

• Lots of the code in this (e.g., the pairs of this.turnLeft() messages, the absence of statements in the base case) follow from considering the problem's postcondition. Use the postcondition to help you think about what your algorithm has to do before it can end, and what it has to work with after a recursive message.

Thinking Recursively

Recursion as "black box" message(s) that solve some problem for you

Towers of Hanoi revisited

    solve( n, source, destination, spare )
        if ( n > 0 )
            solve( n-1, source, spare, destination )
            move( source, destination )
            solve( n-1, spare, destination, source )

Explanation/dissection of this algorithm

• Base case is when n = 0, if there are 0 disks to move then you don't have to do anything. (Note: not base case is where you stop when all the recursion finishes)
• Recursive calls can be understood as moving whole towers of n-1 disks from one pole to another (not as mechanisms for sending control back to the beginning of the algorithm -- think in terms of what messages accomplish, not the details of how)

Next

How do you know it really always works?

Read Chapter 7 through Section 7.1.1

Mini-Assignment: Use induction to show that whenever n >= 4, n! > 2ⁿ

Next Lecture