Intuition:

See the first section examples at this site.

Examples:

1. Non-recursive version of factorial: factorial1.cpp
2. Recursive version of factorial: factorial2.cpp
   In an attempt to understand how recursion works, try tracing execution using both of the following:
   
   1. Write as multiple functions with different names, calling each other
   2. Write in outline form (compress the function body to make this easier to write)
   3. These two trace approaches are illustrated in this Word document
      
3. Other examples
   1. Printing on the way in to the recursion ("head" recursion): reverseDigits.cpp
   2. Printing on the way out of the recursion ("tail" recursion): reverseText.cpp
   3. Misc examples, including exponentiation: recursionExamples.cpp
   4. See this Word document containing the above examples for the topic of recursion.

The Maze program

Consider the maze problem, where there is a rabbit in a maze. The maze is represented as a one-dimensional array. There are several different versions of the solution:

maze1 shows how to make moves and how recursion explores all possible paths. The program gives a message once it reaches the destination, but it doesn't stop recursing, nor does it print a solution.

maze2 shows the solution path, though it is in reverse order.

maze3 uses recursion to give the solution path in order

maze4.cpp is a version in C++.

[CS Dept] [UIC] [Prof. Reed]