reverse print

Another vivid example of recursive power is the "printing a forward list in reverse order". Doubly linked list has other easier way to do reverse print, of course.

Let's use our stockDBlink example at the linked list insertion page. print_rev_recursive() function shall print D, C, B, A in that order. The trick of using recursion is that we need TWO functions: a real one and a helper. The helper is actually doing the real recursive operations.

void print_rev_recursive_helper(stockNode *p) {

if (p!= NULL) {

print_rev_recursive_helper(p->next);

cout << *p;

}

}

The helper only has three lines. Helper has one parameter, a linked list represented by its head pointer. The helper prints the head of the list AFTER calling recursive_helper for the rest of the list. In the example, the first time helper calls to reverse BCD, then print A. One more recursion, it becomes reverse CD, then print B, then print A. In that sequence, A is going to get printed last. The base condition for the recursion is the empty list, p==NULL

The helper does all the work. Real function print_rev_recursive() just get the helper started by feeding it the head of the list.

void stockDBdlink::print_rev_recursive()

{

cout << "== print_rev_recursive" << endl;

if (head == NULL) return;

print_rev_recursive_helper(head);

}

Discussions

1. The algorithm above is a tail recursion type.

2. Are there better ways of doing reverse print or reverse list? Certainly, using a stack works a lot faster.

3. A similar (but even more popular) problem is to "reverse linked list recursively". Try it.