How does recursion works in printing the linked list elements in reverse order?

Question

I have a little bit of idea how recursion works. The invocation and the different context regarding the variables that are provided by stack which is used to store the values returned by previous called function.

For example,

void Factorial(int n)
{
  if(n==0) return 0;
  else if(n==1) return 1;
  else
  {
    return n*Factorial(n-1);
  }
}

in this recursive function for computing the factorial of given number, I know that the first call for suppose the given n is 5, will be 5*Factorial(4*Factorial(3....so on till it reaches any of the base conditions)) then it will traverse back in the order summing up the value such as 1*2*3*4*5=240.

What I have failed to understand is this code to print the items of singly linked list in reverse order.

void ReversePrint(Node head) {    
if(head==null)
    {
    return;
    }
else
    {
    ReversePrint(head.next);
    System.out.println(head.data);
    }
}

As far as I know given there are finite number of elements in linked list function works like,

firstly, since the head is not null it will go to else condition and head will be equals to head.next until it goes to null. and then what?

I may not express my problem in exact words. Hope you will explain. Thanks in advance.

Answer 1

Adding some extra comments should help:

void ReversePrint(Node node) {
    if (node == null) {
        // An empty list has nothing to print.
        return;
    } else {
        // First print the rest of the list.
        ReversePrint(node.next);
        // Then print this node.
        System.out.println(node.data);
    }
}

So - essentially -

• An empty list prints nothing.
• A non-empty list should print the rest of the list first and then prints the root node.

Resulting in the list being printed backwards.

Answer 2

Imagine you had a function called ReversePrintRest, which takes a a list and prints everything but the head in reverse. Then you could write ReversePrint very easily:

void ReversePrint(Node head) {    
    if(head==null) {
        return;
    } else {
        ReversePrintRest(head);
        System.out.println(head.data);
    }
}

So long as ReversePrintRest works as advertised, I'll assume you have no problem in agreeing that this works.

As to how to write ReversePrintRest, that is also easy:

void ReversePrintRest( Node head ) {
    ReversePrint( head.next );
}

Again, assuming that ReversePrint works, the correctness is also easy to see. And since the body of ReversePrintRest was taken directly from your original code, your original code should also be correct.

This may seem a bit of sleight-of-hand: each function's correctness depends on the other's. But we can be a bit more explicit about ReversePrint:

• It clearly works for an empty list
• Assuming that it works for shorter lists, it works for the current one by relying on code known to work on shorter lists and doing the right thing with it (namely, printing the head after reverse-printing the rest).

That leaves only the assumption to justify:

• We know it works for empty lists
• Since it works for empty lists, it works for length-1 lists.
• Since it works for length-1 lists, it works for length-2 lists.

and you can follow that logic as long as you need to for any length N list. Since the argument doesn't rely on the particular value of N, it applies to all of them.

Answer 3

There are probably a lot of duplicates to this question, but rather than finding them and linking them, I'd like to address some things that are problematic with the things that you're asking.

For the factorial example, recursion works nicely, because usually you don't want to calculate very high factorials, and if you do want that you'll usually run into an integer overflow before you run into a stack overflow.

However, lists are very commonly larger than 1000 elements in size. For my implementation, the ReversePrint method gave me a StackOverflowError linked lists larger than about 10000 elements, which is due to Java limiting the stack size in memory.

For an application like this, it is much better to do it non-recursively, by using something like this:

ReversePrint(YourList l) {
    Node n = l.last;
    while (n != null) {
        System.out.println(n.data);
        n = n.prev;
    }
}

Note that some additional features are needed to complete something like this. The list has to be double-linked, both forwards and backwards, and there has to be some kind of YourList class to encapsulate it all (for simplicity).