Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 146

The function executes with m = 4 , n = 9 , and the local variable ch . When the recursive call is made, the following
happens:

1. The values of m , n , and ch are pushed onto a stack.

2. test begins execution, again, with m = 5 , n = 8 , and a new copy of ch .

3. Whenever this call to test finishes (perhaps even after calling itself one or more times and

producing output of its own), the stack is popped, and the program resumes execution
with printf (the statement after the recursive call) and the popped values of m , n , and ch .
In this example, 4 9 would be printed.

5.4 Printing a Linked List in Reverse Order
Consider the problem of printing a linked list in reverse order.

top

36 15 52 23

One way of doing this is to traverse the list, pushing items onto an integer stack as we meet them. When we reach
the end of the list, the last number would be at the top of the stack, and the first would be at the bottom. We then pop
items off the stack and print each one as it is popped.
As we may expect by now, we can use recursion to perform the stacking/unstacking. We use the following idea:

to print a list in reverse order
print the list, except the first item, in reverse order
print the first item

Using the list above, this says print ( 15 52 23 ) in reverse order followed by 36 .
To print (

•

15 52 23 ) in reverse order, we must print ( 52 23 ) in reverse order followed by 15 .

• To print (

52 23 ) in reverse order, we must print ( 23 ) in reverse order followed by 52 .

23 ) in reverse order, we must print nothing (the rest of the list when 23 is removed) in
reverse order followed by 23 .
At the end, we would have printed this: 23 52 15 36 .
Another way to look at this is as follows:

• To print (

reverse(36 15 52 23) → reverse(15 52 23) 36
→ reverse(52 23) 15 36
→ reverse(23) 52 15 36
→ reverse() 23 52 15 36
→ 23 52 15 36