SUNY Geneseo Department of Computer Science

Introduction to Recursion

Previous Lecture

Questions?

Number of data points for expt: nothing specific, but repeat measurements enough to get a handle on variation

Introduction to Recursion

Section 6.1

Recursion = taking complex problem, look at one step at a time

• "One step at a time" = do some small step, then solve a smaller version of the same problem
• Method calls itself
• Decrements parameter, continues until test condition is 0 (but needn't be exactly this mathematical condition)
  • More generally, until problem is so small that it's trivial
• Can simplifiy logic of a problem

"A journey of 1000 miles begins with a single step"

Equivalent syntaxes?

• Move discussion from English towards Java

An Application of Recursion

The Towers of Hanoi

Rules:

• Move one disk at a time
• Only put disks down on poles
• Never put a big disk on a smaller one

Goals:

• Solve the puzzle
• Describe how to solve the puzzle (i.e., an algorithm)

Algorithm:

• Always move smallest disk to furthest peg
• Move it back towards start, making sure it stays on top of pegs

A slightly more detailed version of this algorithm is one of the known ways of solving the Towers of Hanoi. Roughly, it alternates moving the smallest disk two poles right (assuming you want to move from the left-most pole to the right-most, and wrapping around at the ends) and moving the next smallest disk to the (only) pole it can move to.

Look at a Recursive Version in Java. The big lesson here is not so much how the recursion works (we'll come back to that after studying recursion longer), but that the recursive algorithm is so compact -- recursion lets you do a lot of work in a small amount of code.

Design Some Recursive Algorithms

The book's "takeJourney" algorithm, but for robots and with a parameter saying how far to move

    takeJourney( int n )
        if ( n > 0 )
            this.move()
            this.takeJourney( n - 1 )

Print the numbers from n (a parameter) down to 0

    printDown( int n )
        if ( n >= 0 )
            System.out.print( n )
            this.printDown( n - 1 )

• Test: distinguish problems so small that they are trivial (base case) from larger problems (recursive case)
• Part 1: Solve the trivial problem (often doesn't take any action)
• Part 2: Solve the big problems, by doing some small amout of work and then solving one or more smaller problems by calling yourself

Next

Read Sections 6.2 - 6.4

Mini-assignment: design a recursive algorithm, int powerOf2( int n ), that computes and returns 2ⁿ

Next Lecture