• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help with recursion  RSS feed

 
Michael Ferguson
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am working on a Red Black tree for a data structures class.

I have the code:

void printInorder(Node node)    //Input is initially the root node
{
     if (node == null)
     {
           return;
     }
     printInorder(node.left);
     System.out.println(node.data);
     printInorder(node.right);
}

Let's use this Binary tree as an example:

          50
         /    \
      40     60
     /    \       \
  20    45      70
         /   \      /
       43  47  65

The output of the code is correct and is : 20 40 43 45 47 50 60 65 70

My understanding of the code is that it would recursively call printInorder(node.left) until it reached 20.

At that point, it would then print "20 ", then it checks printInorder(node.right), sees that it is null and returns back to the printInorder(node.right) statement, at which point it is at the bottom of the method and has no more code to run so it exits.

The output is correct, but from my understanding of the code it should stop after printing "20 ".

Can someone explain the process of this recursive loop, step-by-step for me? Thank you.
 
Tim Moores
Saloon Keeper
Posts: 4035
94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why would it stop? There is no condition to make it do so once the first node value is printed.
 
Michael Ferguson
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim Moores wrote:Why would it stop? There is no condition to make it do so once the first node value is printed.


Why would it continue? Once it reaches the end of the method shouldn't it just stop running the code? Or will it loop back to the top?
 
Campbell Ritchie
Marshal
Posts: 56578
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you have a node class? It is usually easier to get the nodes to print themselves. In which case you have the null test in the wrong place. What I would do is test whether the left node is null; if not tell the left to print. Then print the current node's value (you can't get any problems with nulls at this point. Then test and print right. That is (if I remember correctly) a depth‑first inorder traversal because you print the current node's value in the moddle. For preorder or postorder, print the current value first or last. Obvioulsy there are left‑to‑right and right‑to‑left versions. I think it is usual to go left‑to‑right.
 
Tim Moores
Saloon Keeper
Posts: 4035
94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Michael Ferguson wrote:Once it reaches the end of the method shouldn't it just stop running the code?

It does, but there are several copies of the method running - every time it calls itself, a new copy will be created with a different node as parameter. Only when all of them have come to an end will the top-most method be done.
 
German Martinez
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's start first with a non-recursive function, which is given any node as a parameter.

Suppose the procedure receives as parameter the root node. The code output will be first the left node, then the center node, then the right node: 40, 50, 60. If the routine receives as parameter the node 45, the output will be: 43, 45, 47. If you look at it, if we apply this non-recursive procedure to any node in the tree, it will work (assuming there is a left and right node).

Now comes recursiveness. As the above procedure works anywhere in the tree, we can make it recursive so that it explores the whole tree, taking care when we reach an end (a leaf) where we don't have any more nodes. Below is your code with comments added:


The first IF statement is a safegard for the case that there is no valid node as input parameter.

Let's see how it works with a tree like this:

           1
       /       \
     2         5
  /    \     /    \
3      4   6     7

WE ARE AT NODE 1
The procedure receives node 1. it sees that 1 is not null. Then:
     - 1. It commands *other* to print the left subtree (root is 2)
     - 2. It prints the current node, 1, and then
     - 3. It commands *another* to print the right subtree (root is 5)

But what happens in step 1?
The procedure calls *OTHER COPY* of itself, giving it node 2, and then we start over.

WE ARE AT NODE 2
The new copy of the procedure receives node 2. it sees that 2 is not null. Then:
     - 1.1. It commands *another copy* to print the left subtree (root 3)
     - 1.2. It prints the current node, 2, and then
     - 1.3. It commands *another copy* to print the right subtree (root 4)

By executing step 1.1 of the above procedure we come here:

WE ARE AT NODE 3
Another new copy of the procedure receives node 3, and we start over again.
     - 1.1.1 This copy, calls another to process the left tree, but there is not left subtree so it returns immediately.
     - 1.1.2 Then prints its own node (node 3),
     - 1.1.3 And calls another copy to print the right subtree, which does not exist, so this copy also return immediately.

So finally, node 3 is processed. But who called the procedure that processed node 3? It was called by the previous procedure, the manager of node 2 (at step 1.1)

WE ARE AT NODE 2 AGAIN
So now, that procedure goes to step 1.2 and prints "2". and then executes step 1.3, and calls another copy to process node 4.

WE ARE AT NODE 4
Node 4 is processed in the same way as described above. At the end of this procedure, the control is returned to the caller.

WE ARE AT NODE 2 AGAIN
But node 2 no longer requires further processing, so it returns control to the caller.

WE ARE AT NODE 1 AGAIN
The control now returns to the procedure that handled node 1 which now prints "1" (step 2) and the right subtree is processed in a similar way. (step 3).
 
German Martinez
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My understanding of the code is that it would recursively call printInorder(node.left) until it reached 20.


Not exactly. the printInorder(node) procedure receives a node, then processes the WHOLE subtree from that node, and then returns control to the caller.

To process the entire subtree, printInorder first processes the entire left subtree, then prints the node that was given to it, and then processes the entire right subtree.


 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know if it's conceptually easier to think about recursion in terms of running copies of a method. It might be so if explained in the way it has been by others in previous replies.

Technically, however, that is NOT what is happening. There is only ONE set of instructions in memory being executed. The recursion mechanism happens via what are known as "the stack" and "stack frames".

Given this recursive method (which is very procedural in nature, by the way):

Let's say the initial call is made with Node(50), the root node of the tree you gave:

On this initial call to printInOrder, a stack frame is created which contains, among other things:
- upon returning from the call to printInOrder, resume execution at doSomethingElse()
- the argument passed is root, that is, node == Node(50)

Let's refer to this as call #1. The stack will contain the stackFrame for call#1.

Stack:
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #1 of printInOrder():
- line 3: node on the stack is not null, so continue to next statement
- line 7: call printInOrder() method, passing the node.left, Node(40). This is call #2 to printInOrder().

Another stack frame is pushed unto the stack for call #2 and the stack will now look something like this:

Stack:
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #2 of printInOrder():
- line 3: node is not null (it's Node(40)) so continue to next statement
- line 7: call printInOrder() with node.left, i.e. Node(40).left, which is Node(20). This is call #3 to printInOrder()
- (call #2 is suspended until call #3 completes)

Another stack frame is pushed unto the stack for call #3 and the stack will now look something like this:

Stack:
[ resume @ line 8 of call #2, node = 20] <-- stack frame for call #3
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #3 of printInOrder():
- line 3: node is not null (it's Node(20)) so continue to next statement
- line 7: call printInOrder() with node.left, i.e. Node(20).left, which is null. This is call #4 to printInOrder()
- (call #3 is suspended until call #4 completes)

Another stack frame is pushed unto the stack for call #4 and the stack will now look something like this:

Stack:
[ resume @ line 8 of call #3, node = null] <-- stack frame for call #4
[ resume @ line 8 of call #2, node = 20] <-- stack frame for call #3
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #4 of printInOrder():
- line 3: node is null, so return. This ends this round of recursion.
- (call #4 terminates)

The stack is popped and the stack frame that was just popped (the one for call #4) says to resume execution on line 8 of call #3.

Stack:
[ resume @ line 8 of call #2, node = 20] <-- stack frame for call #3
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #3 (continuing @ line 8)
- line 8: print out node, (20)
- line 9: another call to printInOrder(), this time passing node.right, or Node(20).right. This is null. This is call #5 to printInOrder
- (call #3 is again suspended, this time until call #5 completes)


Stack:
[ resume after line 9 of call #3, node = null] <-- stack frame for call #5
[ resume @ line 8 of call #2, node = 20] <-- stack frame for call #3
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #5 of printInOrder():
- line 3, node == null, so return
- (call #5 terminates)

Stack is popped and execution resumes after line 9 of call #3.


Stack:
[ resume @ line 8 of call #2, node = 20] <-- stack frame for call #3
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


Since there are no more executable statements after line 9, then call #3 terminates.

Stack is popped and execution resumes at line 8 of call #2.

Stack:
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #2 (continues @ line 8):
- line 8: print node, (40)
- line 9: another call to printInOrder(), this time passing node.right, which is Node(40).right, which is Node(45). This is call #6 to printInOrder
- (call #2 is suspended until call #6 completes)

Stack:
[ resume after line 9 of call #2, node = 45] <-- stack frame for call #6
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #6 of printInOrder():
- line 3: node is not null, continue
- line 7: another call to printInOrder(), passing in node.left, which is Node(45).left, which is Node(43). This is call #7 to printInOrder()
- (call #6 is suspended until call #7 completes)


Stack:
[ resume @ line 8 of call #6, node = 43] <-- stack frame for call #7
[ resume after line 9 of call #2, node = 45] <-- stack frame for call #6
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1


call #7 of printInOrder():
- line 3: node is not null (it's Node(43)), continue on line 7
- line 7: another call to printInOrder(), passing in node.left, which is Node(43).left, which is null. This is call #8 to printInOrder()
- (call #7 is suspended until call #8 completes)


Stack:
[ resume @ line 8 of call #7, node = null] <-- stack frame for call #8
[ resume @ line 8 of call #6, node = 43] <-- stack frame for call #7
[ resume after line 9 of call #2, node = 45] <-- stack frame for call #6
[ resume @ line 8 of call #1, node = 40] <-- stack frame for call #2
[ resume @ doSomethingElse(), node = 50] <-- stack frame for call #1

and so on

Hopefully by now you see the pattern.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As Campbell was alluding to in an earlier reply, it would be more object-oriented if your Node had logic like this:

The code can be made cleaner and more OO if you used the Null Object pattern:

On line 4, you assign an anonymous subclass of Node to the NULL reference and use that to initialize the left and right children of the current node. Of course, these can be replaced by valid nodes when you addLeft() and addRight().
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!