We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Print in Reverse
You are viewing a single comment's thread. Return to all comments →
I took sophist_pt's code and altered it a bit to hopefully make it more intuitive.
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.
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!
This function was written from sophist_pt's brilliant code.