SUNY Geneseo Department of Computer Science

Introduction to Recursion

Previous Lecture

Misc

Hand out Lab 3

No Friday office hours this week

Questions?

Using robot with Sun Java tools?

• Sun equates package components with folders

• Project folder needs tocontain a folder "geneseo"
  • which contains "cs"
  • which contains "sc"
  • which contains "Robot.java" and "RobotRoom.java"

Averaging measurements for lab 2?

• For each value of the independent variable (distance), say 3...
• ...Measure the dependent variable (time) several times, e.g.,
  • 4.01
  • 4.0
  • 4.03
• But which of these is right?
• Answer: None. Their average is closest

Reading Summary

Sections 6.1 - 6.3

(Lots of this summary got lost when my computer crashed after running its battery down)

Recursion is solving a problem in terms of smaller versions of itself

Value-producing recursion must always return a value

Value-producing recursions always have at least 2 return statements

Three kinds of recursion

• Value-producing
• Goal-reaching (e.g., takeJourney)
• Index-finding (e.g., countDigits)

Why Care about Recursion?

Towers of Hanoi

Goal: Move the tower from the left pole to the right (or vice versa)

Rules:

• Only move one disk at a time
• Never put a bigger disk on top of a smaller
• Only put disks down on poles

Recursion Examples

Imagine a "Super Array" class that represents arrays with some additional features

Arrays

• List or table of values, all values of same type
• For example
  • List of integers
  • List of robots
• Array has fixed size
• Values in array (elements, items) are accessed by position (index)

• Syntax
  • int[] sizes = new int[ 10 ];
  • String[] names = new String[3];
  • sizes[0] = 1;
  • x = sizes[3] * 4;

    class SuperArray {

        private int[] A;      // Underlying array
        private int n;        // Size of array

        public SuperArray( int size ) {
            A = new int[ size ];
            n = size;
        }

        public getElement( int i ) {
            return A[i];
        }

        ...

Design a recursive method for SuperArray that initializes elements 0 through i to 0

    init( int i )
        if i < 0          // test
            do nothing    // base case
        else
            A[i] = 0;     // Recursive case
            init( i - 1 )

Next

Some more sophisticated recursions

Read Sections 6.4 and 6.5

Next Lecture