SUNY Geneseo Department of Computer Science

Intermediate Recursion

Previous Lecture

Misc

Hand out Lab 4

Questions?

Sections 6.4 and 6.5

Ways to make sure recursion terminates

• Check logic
• Avoid exact tests
• Don't increment by 0
• For non-integral increments, be sure you can reach target

Three parts

• General step, makes problem smaller
• Final step
• Test

Inversion

• Robot forward and back example

Don't do recursion before test

Designing Intermediate Recursion

Recursive algorithm to print n 1's followed by n 2's

    print12( n )
        if n > 0
            print 1
            print12( n-1 )
            print 2
        else

• Act out how this executes
  • Me: "Sean, print12(5)"
  • Sean: 1
    • "Jordan, print12(4)"
  • Jordan: 1
    • "Sam, print12(3)"
  • Sam: 1
    • "Garrett, print12(2)"
  • Garrett: 1
    • "Pat, print12(1)"
  • Pat: 1
    • "Matt, print12(0)"
  • Matt: return
  • Pat: 2
    • return
  • Garrett: 2
  • Sam: 2
  • Jordan: 2
  • Sean: 2

Print n 1's followed by 2n 2's

    print1Double2( n )
        if n > 0
            print 1
            print1Double2( n-1 )
            print 2
            print 2
        else
            do nothing

Use the robot to draw a "bracket" n tiles on a side, n >= 1

    // In some subclass of Robot...
    bracket( n )
        if n > 1
            this.paint(Yellow)
            this.move()
            this.bracket( n-1 )
            this.move()
            this.paint( Yellow )
        else
            this.paint( Yellow )
            this.turnLeft()

Next

Some final discussion of the "bracket" algorithm

How do you know a recursive algorithm is really correct?

• Read Section 7.1.1

Next Lecture