SUNY Geneseo Department of Computer Science

Recursion, Part 2

Previous Lecture

Misc

I won't be here Monday (Sept. 27); lab will be "open lab" format (do at your own pace/time; ask questions via office hours, lecture, etc.)

• Lab 3 is due on the 28th (Tuesday)

Questions?

Reading Summary

Sections 6.4 - 6.5

6.4 dealt with termination -- making sure program terminates

• Look at algorithm design, e.g., counting down towards 0, counting down by 2s from an odd number misses 0

Inversion - last invocation is first to finish

Algorithm that calls self recursively can't continue 'til recursion finishes

Counting up

Counting down

Never place recursive call before test

Three patterns of recursion with only one recursion in algorithm

• Action before call
• Action after call
• Both

    algorithm()
        if test
            *
            algorithm()
            *
        else
            base case

But lots of other patterns too

    algorithm()
        if test1
            *
            algorithm()
            *
        else if test2
            *
            algorithm()
            *
        ....
        else if test n
            base case 1
        else
            base case 2

• e.g., square root example

Also

    algorithm()
        if test
            *
            algorithm()
            *
            algorithm()
            *
        else
            base case

• e.g., towers of Hanoi

The above can all mix-and-match

" Super Array" Recursion Examples

    class SuperArray {

        private int[] A;         // Underlying array
        private int n;           // Size of array
		
        public SuperArray( int size ) {
            A = new int[ size ];
            n = size;
        }
        ...

A recursive method for SuperArray that counts the number of elements between positions 0 and i that are equal to 0

    int countZeros( int i )
        if i >= 0
            if A[i] == 0
                return this.countZeros(i-1) + 1
            else
                return this.countZeros(i-1)
        else
            return 0

Palindromes

e.g., radar, etc

Write an algorithm that prints a random palindrome of length n

aqwtggtwqa

    palindrome( n )
        if n <= 0
            // do nothing
        if n == 1
            print a random character
        else
            c = random character
            print c
            palindrome( n-2 )
            print c

Advancing and Retreating Robots

Write a recursive algorithm that makes a robot move forward n tiles, and then come back to where it started, facing opposite of original direction

    // In some subclass of Robot...
    forwardAndBack( int n )
        if n > 0
            this.move()
            this.forwardAndBack( n-1 )
            this.move()
        else
            this.turnRight()
            this.turnRight()

Next

Reasoning about the correctness of recursive algorithms

Read Section 7.1 through the "Introduction" part of 7.1.2 (top of page 216)

Next Lecture