SUNY Geneseo Department of Computer Science

Introduction to Recursion

Previous Lecture

Questions?

Recursion = replacing "while" with "if"?

• Recursion is quite a bit more powerful than looping

Recursion = defining something in terms of a smaller version of itself

• Abstraction = suppressing details to concentrate on essentials
• Connection: suppressing details of what's inside recursion helps understand it

Introduction to Recursion

Section 6.1

Recursion

Definition (see above)

• e.g.,

    to sing 99 bottles of beer song
        sing verse for some number
        sing song for next smaller number
    unless number is 0, in which case
        sing different verse

Lots of examples

• takeJourney

    take one step
    take all remaining steps

• Java translation

Recursion in code

• Calls itself
• Something (e.g., parameter) gets smaller as you call yourself
• Termination: parameter (or something) gets so small that it's time to stop calling yourself

    if ( ... some condition ... )
        call yourself (repetition)
    else
        finish, do something simple

Sophisticated uses

• Drawing fractals
• Solving mazes
• Interpreting language
• etc.

The Towers of Hanoi

A relatively sophisticated use of recursion, a preview of where recursion can get you.

Goal: Move an n-disk tower from one pole to another.

Rules:

• Only move 1 disk at a time
• Only put disks on poles
• Never put a bigger disk on a smaller one

See if you can...

• Solve the puzzle
• Describe, in terms that generalize to any number of disks, how you did it
  • Make smallest disk follow the next biggest....
  • If number of disks is odd, build next biggest pyramid by putting top disk on empty peg
    • Else build next biggest pyramid by putting top disk on as-yet-unmoved large disks
    • Then follow Jason's idea of small disk following next larger
  • Rotate from already-moved pile to empty
  • Building up from 1-disk stack to 2-disk to 3-disk, etc.
  • First disk has to move to middle peg (if number of disks is even)

The puzzle can actually be Solved in 4 lines of Java, using 2 recursions.

Recursion Examples

Draw a red line from the robot's current position to a wall.

    public void lineToWall() {
        this.paint( Color.red );
        if ( this.okToMove() ) {
            this.move();
            this.lineToWall();
        }
    }

Count the tiles between robot's starting position (inclusive) and wall

    public int countToWall( int count ) {
        if ( this.okToMove() ) {
            count = count + 1;
            this.move();
            this.countToWall( count );
        }
        return count;
    }

• In client...

        Robot r = new Robot();
        r.countToWall( 1 );

• Local counters are bad
• This can be done without any explicit counter

Next

More Recursion

Mini-assignment: countToWall with no "count" parameter, variable, etc

Read Sections 6.2 through 6.5

Next Lecture