• + 36 comments

    I took sophist_pt's code and altered it a bit to hopefully make it more intuitive.

    void ReversePrint(Node head) {
    
        //if the head is not yet null...
        if (head != null) {
            //call the function again but on the next node
            ReversePrint(head.next);
            /*----------------------------------------------
            The recursion will get "stacked" right here!
            The code below this area will not get called
            until we go back up through the recursive stack.
            -----------------------------------------------*/
            System.out.println(head.data);
        }
    }
    

    Here's a code trace for an example. We have a linked list of three elements [1] -> [2] -> [3] Let's begin by calling the head.

    A. RevPr(1)
    if elemenent 1 is not yet null, move on.
    It's not null! Call again on next, element 2...
        B. RevPr(2)
        if elemenent 2 is not yet null, move on.
        It's not null! Call again on next, element
        3...
            C.  RevPr(3)
            if elemenent 3 is not yet null,
            move on. It's not null! Call again
            on next, element 4...
                D. RevPr(4)
                if elemenent 4 is not yet null, move on. 
                Wait, it is null! No more calls, we're done.
    

    So we just built this recursive stack. [RevPr1(RevPr2(RevPr3(RevPr4)))] Now we have to execute the function that is innermost. Why? Because that's where we were most recently!

                D. RevPr4. That most recent call failed the
                condition. Nothing is printed.
                -->[RevPr1(RevPr2(RevPr3()))]
            C. RevPr3. RevPr3 never finished the code in
            the if statement, so now we print 3!
            -->3
            -->[RevPr1(RevPr2())]
        B. RevPr2. Now we need to print 2!
        -->3
        -->2
        -->[RevPr1()]
    A. RevPr1. The last call! Print 1! This call is done, and
    now everything is done.
    -->3
    -->2
    -->1
    

    This function was written from sophist_pt's brilliant code.