SUNY Geneseo Department of Computer Science

Recursion, Part 2

Previous Lecture

Misc

Hand out Lab 4

Questions?

Recursion

Sections 6.2 through 6.5

Indices

• Controlling factor in recursion
• e.g., shortened distance in takeJourney
• Careful about starting methods wrong
• Indices needn't be numbers

Mathematically, recursion is like induction

• e.g., factorial

String manipulation, e.g., myReplace

Recursions that return results, e.g., howManyDigits

Be careful about termination

• Decrement has to include terminating condition
• e.g., stop at 0 but index can become negative
• Consider <= 0 rather than == 0

Recursive algorithms

Sequences vs lists of steps

• Recursion does correspond to steps being executed in some sequence, but not written as a list of all the steps in order executed
• Think of recursion as delegation of work
• Like wind-up toy
• e.g., "toWall" with managers

Recursons split into 3 parts

• Recursive step aka recursive case
• Base step aka base case
• Test

Methods with multiple recursions

• e.g., guessSquareRoot

Things to avoid

• Don't do recursion first

Make dummy methods (?)

• Different interface for clients than for recursion

        guessRoot( n, low, high )

• vs client interface

        root( n )

        root ( n ) {
           guessRoot( n, 0, n )
        } 

downAndUp algorithm

    downAndUp( n )
        if n > 0
            print n
            downAndUp( n-1 )
            print n

• Lisa.downAndUp( 3 ) print 3
• Christina.downAndUp( 2 ) print 2
• Dan.downAndUp( 1 ) print 1
• Ryan.downAndUp( 0 )
• Dan print 1
• Christina print 2
• Lisa print 3
• First recursion done is last finished

Mini-Assignment

Count the tiles between robot's starting position (inclusive) and wall, without using a "counter" variable or parameter

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

Paint each step walked, as in lineToWall, then search room for painted squares?

Recursively compute partial answer, then build full answer and return it

More Recursion Examples

Recursively search elements 0 through n of array A for a value x, returning True or False

    boolean find( int x, int[] A, int n ) {
        if ( n < 0 ) {            // test, part 1
            // base case 1
            return false;
        }
        else if ( A[n] == x ) {   // test, part 2
            // base case 2
            return true;
        }
        else {
            // recursive case
            return find( x, A, n-1 );
        }
    }

• Recursive insight:

Print a balanced string of n pairs of parentheses

• n "(" followed by n ")"
• e.g., ((()))

    void parens( int n ) {
        if ( n > 0 ) {
            print "("
            parens( n-1 )
            print ")"
        }
    }

• Think of recursion as creating and running a copy of the method, not just as jumping back to the beginning and starting over.

Print the balanced parentheses, but put a "*" in the center

• e.g., (((*)))

    void parensAndStar( int n ) {
        if ( n > 0 ) {
            print "("
            parensAndStar( n-1 )
            print ")"
        }
        else {
            print "*"
        }
    }

Print an unbalanced string of parentheses, n "(" followed by 2n ")"

• (())))

    void unbalancedParens( int n ) {
        ...
    }

• Mini-assignment: design algorithm
  • How do you know it's correct?
  • Read Section 7.1.1

Next Lecture