Dual recursion in a function, how does it work?

Question

I understand what happens in recursion when there is only one recursive call, I understand well how to write an output condition for recursions. But I have difficulty understanding when there are two recursions, for example:

InOrder-Tree-Walk(x)
  if x != null
    InOrder-Tree-Walk(x.left)
    print(x.key)
    InOrder-Tree-Walk(x.right)

the pseudo code above represents a method to give print in all elements of a Binary Search Tree, I do not understand how the execution is done. The first recursion happens before the second or they are simultaneous?

Answer 1

There’s nothing special about it, recursion is not a magical mechanism full of details that you can’t see. Recursion is just a function calling another function with a single difference between the most common calls, the function being called is the same as the caller, or at least a triangular call occurs.

There is no simultaneity, first executes one and then, at her time, executes the other. Recursion changes nothing in the sequence of execution, is exactly like any other function call and sequential execution.

On the first call if he enters the conditional block he will call the function again by passing the member indicated there. As the function is reentrant he will make his parole and if he enters it because there is a branch there (it is not null) then he has to try again to analyze this branch of the left found, and he goes doing it in sequence (always looking at the left side of each branch analyzed) until he does not enter the conditional anymore by not having a branch on the left (now the value is null).

When this function ends without executing, it continues the normal flow of the function execution, we will analyze it.

In this penultimate call (the last one did not enter the if) makes an impression and then starts recurring again by calling the function itself now by passing the right branch, and starts the same process reported above, so if that new call is not the value null he repeats the calls one by one in the existing branches. This will end when it is null and will return to the previous call.

After finishing this he no longer has any other line to run, so he closes this function. But since she must have been called by herself, he must continue where he left off.

Make a table test with a tree mounted and see how the execution looks.

         5
       /   \
    3         8
   /  \      /  \
 1     4   6     10
                /   \
              9      11

• (level 1) Will call where the key is 5 (but I am anticipating). It calls the function passing the necessary.
• (level 2) Find a left and call again.
• (level 3) Now you don’t have a left, then it will end (I think this print(x.key) should be out of the if and print 1). The key is 1. Closes without executing.
• (level 2) Going back to the previous call now it will call with right.
• (level 3) It is null so it will execute nothing. The key is 4.
• (level 2) Returning he executes the right.
• (level 2) Now you have no object, then you will close. The key is 3.
• (level 2) Going back to the previous call now it has no other command to execute.
• (level 1) Now back and following the function and performs the second function call by passing the right.
• (level 2) Find a right and call again.
• Finish you with the right side, it goes up to level 4 :)

It can be useful to write code in real language, get good software from debug, have the code run with a real tree and see the call stack to better understand.