|
|
|
|
|
|
|
void Print( /* in */ const int list[], // Array to be printed
/* in */ int first, // Index of first element
/* in */ int last ) // Index of last element
{
if (first <= last)
{ // Recursive case
cout << list[first] << endl;
Print(list, first + 1, last);
}
// Empty else-clause is the base case
} |
|
|
|
|
|
|
|
|
Here is a code walk-through of the function call |
|
|
|
|
|
|
|
|
using the array shown at the left. |
|
|
|
|
|
|
|
|
Call 1: first is 0 and last is 4. Because first is less than last, the value in list[first] (which is 23) is printed. Execution of this call pauses while the array from first + 1 through last is printed. |
|
|
|
|
|
|
|
|
Call 2: first is 1 and last is 4. Because first is less than last, the value in list[first] (which is 44) is printed. Execution of this call pauses while the array from first + 1 through last is printed. |
|
|
|
|
|
|
|
|
Call 3: first is 2 and last is 4. Because first is less than last, the value in list[first] (which is 52) is printed. Execution of this call pauses while the array from first + 1 through last is printed. |
|
|
|
|
|
|
|
|
Call 4: first is 3 and last is 4. Because first is less than last, the value in list[first] (which is 61) is printed. Execution of this call pauses while the array from first + 1 through last is printed. |
|
|
|
|
|
|
|
|
Call 5: first is 4 and last is 4. Because first is equal to last, the value in list[first] (which is 77) is printed. Execution of this call pauses while the array from first + 1 through last is printed. |
|
|
|
|
|
|
|
|
Call 6: first is 5 and last is 4. Because first is greater than last, the execution of this call is complete. Control returns to the preceding call. |
|
|
|
|
|
|
|
|
Call 5: Execution of this call is complete. Control returns to the preceding call. |
|
|
|
|
|
|
|
|
Calls 4, 3, 2, and 1: Each execution is completed in turn, and control returns to the preceding call. |
|
|
|
|
|
|
|
|
Notice that once the deepest call (the call with the highest number) was reached, each of the calls before it returned without doing anything. When no statements are executed after the return from the recursive call to the function, the recursion is known as tail recursion. Tail recursion often indicates that the problem could be solved more easily using iteration. We used the array example because it made the recursive process easy to visualize; in practice, an array should be printed iteratively. |
|
|
|
|
|
