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.
In this case you have to consider that your tree has a knot, which is printed, a subtree on the right and another subtree on the left, which are actually trees, and therefore traversed by the function.
– anonimo
Related (it may help to understand, as it is also a case of having 2 recursive calls in the same function): https://answall.com/q/412524/112052
– hkotsubo