|
|
|
|
|
|
|
Recursion Using Pointer Variables |
|
|
|
|
|
|
|
|
The previous recursive algorithm using a one-dimensional array could have been done much more easily using iteration. Now we look at two algorithms that cannot be done more easily with iteration: printing a linked list in reverse order and creating a duplicate copy of a linked list. |
|
|
|
|
|
|
|
|
Printing a Dynamic Linked List in Reverse Order |
|
|
|
|
|
|
|
|
Printing a list in order from first to last is easy. We set a running pointer (ptr) equal to head and cycle through the list until ptr becomes NULL. |
|
|
|
|
|
|
|
|
Set ptr = head
WHILE ptr is not NULL
Print ptr->component
Set ptr = ptr->link |
|
|
|
|
|
|
|
|
|
To print the list in reverse order, we must print the value in the last node first, then the value in the next-to-last node, and so on. Another way of expressing this is to say that we do not print a value until all the values in all the nodes following it have been printed. We might visualize the process as the first node's turning to its neighbor and saying, Tell me when you have printed your value. Then I'll print my value. The second node says to its neighbor, Tell me when you have printed your value. Then I'll print mine. That node, in turn, says the same to its neighbor, and this continues until there is nothing to print. |
|
|
|
|
|
|
|
|
Because the number of neighbors gets smaller and smaller, we seem to have the makings of a recursive solution. The end of the list is reached when the running pointer is NULL. When that happens, the last node can print its value and send the message back to the one before it. That node can then print its value and send the message back to the one before it, and so on. |
|
|
|
|
|
