CHAPTER 70 — Introduction to Recursion
This chapter introduces recursion.
Previous chapters have discussed the fundamental
control mechanisms of sequence, alternation (if-else), and iteration (while).
Recursion is another control mechanism.
Sometimes problems are stated in a recursive fashion, and a program that
solves the problem is easily written using recursion.
- Two Parts to Recursion:
- Solve easy problems in one step.
- Divide hard problems into smaller problems,
and then solve the smaller problems.
- Examples of Recursion:
- Walking a Distance
- Smashing a Rock
- Dividing a Line
- Drawing a Snowflake
Forget programming for a while.
Think about a real-world problem that does not involve computers:
It is the day after Thanksgiving and the only parking spot
you can find at the shopping mall
is far from the entrance (horrors!)
How do you get from your car to the mall?