SUNY Geneseo Department of Computer Science

Introduction to Recursion

Previous Lecture

Questions?

Introduction to Recursion

Section 6.1

If you need to repeat steps you can call a method from itself (recursion)

Breaking large problems into smaller versions of the large problem

Eventually reach trivial step

• Base case

Preview of Recursion's Power

The Towers of Hanoi

Rules

• Only move one disk at a time
• Disks must always be put down on poles
• Never put a big disk on top of a smaller one

Try to devise an algorithm for solving the puzzle for any number of disks, and then describe that algorithm

Ideas

1. Move smallest to empty pole
2. Move 2nd smallest to other empty pole
3. Move smallest onto 2nd smallest
4. Then move 3rd smallest
5. Keep going....

Or

1. Somehow get down to biggest disk, get others on middle pole so biggest can move.

Or

1. Move largest available to free pole,
2. Move next largest available to free pole,
3. Move first disk moved onto second moved,
4. Now move another top-most disk....

This has a concise description as a recursive algorithm. See Program that solves the puzzle.

Structure of Recursive Algorithms

Some examples from the text -- in what ways are their control structures similar?

Next

Designing Recursive Algorithms

Read Sections 6.2 and 6.3

Next Lecture