CS 455 Lecture Notes
Week Twelve, Tuesday: Recursive Thinking
Before we examine the tree data structure (chapter 10) we reinforce our
ability to think recursively. This will come in handy with tree structures.
Recursive Functions
Function write_vertical(int number) example: If the number is less than 10, write it,
else call write_vertical(number / 10) and then write the number modulo 10.
The runtime executive keeps track of function calls by pushing activation records onto
the runtime stack.
Studies of Recursion: Fractals and Mazes
|
|
Fractal demonstration Applet. Click for a new random fractal line.
The "traversing a maze" example utilizes the runtime stack to both backtrack
in searching the maze and to back the explorer out of the maze once the goal
has been achieved.
This page established November 14, 1999; last updated November 15, 1999.