MHB What happens when a null pointer is passed into a recursive function?

[evinda]

Hello! (Nerd)

Suppose that we have this tree:

View attachment 3559

and we want to apply the following algorithm:

Procedure Pr(pointer P){
   if (P==NULL) return;
   Pr(P->lc);
   print(P->data);
   Pr(P->rc);
}

We call the procedures [m]Pr(A), Pr(B), Pr(D), Pr(H), Pr(NULL)[/m], right?

When we run the Procedure [m]Pr(NULL)[/m], the command [m]return;[/m] is executed.
After that, what do we have to do? Do we have to execute the commands, that are under the command [m]Pr(P->lc);[/m] for [m]P->lc=H[/m] ? (Thinking)

 

[Ackbach]

Hello! (Nerd)

Suppose that we have this tree:

View attachment 3559

and we want to apply the following algorithm:

Procedure Pr(pointer P){
   if (P==NULL) return;
   Pr(P->lc);
   print(P->data);
   Pr(P->rc);
}

We call the procedures [m]Pr(A), Pr(B), Pr(D), Pr(H), Pr(NULL)[/m], right?

I don't know; is it part of the problem statement to make all these calls, and then predict what the outcome will be?

When we run the Procedure [m]Pr(NULL)[/m], the command [m]return;[/m] is executed.

Right.

After that, what do we have to do?

I don't know; what is the exact problem statement?

Do we have to execute the commands, that are under the command [m]Pr(P->lc);[/m] for [m]P->lc=H[/m] ? (Thinking)

When the code gets to the point where it is at H, it will call [m]Pr(H->lc)[/m]; however, that will be a null pointer, so it will return without executing the remainder of the commands in [m]Pr[/m]. Does that answer your question?

 

[evinda]

I don't know; is it part of the problem statement to make all these calls, and then predict what the outcome will be?
Right.
I don't know; what is the exact problem statement?

The algorithm should traverse the tree, so that the keys will be printed in ascending order.

When the code gets to the point where it is at H, it will call [m]Pr(H->lc)[/m]; however, that will be a null pointer, so it will return without executing the remainder of the commands in [m]Pr[/m]. Does that answer your question?

I wasn't sure what command the algorithm will execute, after executing the command return; .. (Thinking)

 

[Ackbach]

The algorithm should traverse the tree, so that the keys will be printed in ascending order.

Ok: in your mind, is G the right-most node (is it the right child or left child of C)? Because if it's the right child, and you need to print in ascending order, then you should process right child, node, then left child - the opposite of the order you have.

I wasn't sure what command the algorithm will execute, after executing the command return; .. (Thinking)

When the return is executed, then that call of [m]Pr[/m] is done executing, and will leave the stack, and you'll go back to the parent's instance of [m]Pr[/m].

 

[evinda]

Ok: in your mind, is G the right-most node (is it the right child or left child of C)? Because if it's the right child, and you need to print in ascending order, then you should process right child, node, then left child - the opposite of the order you have.

Oh yes, you are right! (Blush) So, should it be like that?

Procedure Pr(pointer P){
   if (P==NULL) return;
   Pr(P->rc);
   print(P->data);
   Pr(P->lc);
}

When the return is executed, then that call of [m]Pr[/m] is done executing, and will leave the stack, and you'll go back to the parent's instance of [m]Pr[/m].

So, the procedures [m]Pr(A),Pr(C),Pr(G),Pr(NULL)[/m] will be executed, then the number 42 will be printed. Then, the procedure [m] Pr(NULL)[/m] will be called and the command return; will be executed, right? (Thinking) And, what happens after that?

 

[Ackbach]

Oh yes, you are right! (Blush) So, should it be like that?

Procedure Pr(pointer P){
   if (P==NULL) return;
   Pr(P->rc);
   print(P->data);
   Pr(P->lc);
}

Yes, at least that's correct in pseudocode. The exact syntax you'll need to make work in whatever language you're using.

So, the procedures [m]Pr(A),Pr(C),Pr(G),Pr(NULL)[/m] will be executed, then the number 42 will be printed. Then, the procedure [m] Pr(NULL)[/m] will be called and the command return; will be executed, right? (Thinking)

Exactly right. Now the [m]G[/m] node has been fully processed, and the [m]Pr(G)[/m] call to the function will finish executing. Then the program gets rid of that instance of [m]Pr[/m] from the stack, and continues executing the [m]Pr(C)[/m] instance. It's finished the right child, so now it does what?

 

[evinda]

Yes, at least that's correct in pseudocode. The exact syntax you'll need to make work in whatever language you're using.
Exactly right. Now the [m]G[/m] node has been fully processed, and the [m]Pr(G)[/m] call to the function will finish executing. Then the program gets rid of that instance of [m]Pr[/m] from the stack, and continues executing the [m]Pr(C)[/m] instance. It's finished the right child, so now it does what?

We will have something like that, right?

View attachment 3562

After that, why do we execute the commands [m] print(C->data)[/m] and [m]Pr(C->lc)[/m]?
If there were also other commands, after the command [m]Pr(P->lc)[/m], would they be executed for G or would the [m]G[/m] node be again fully processed? (Thinking)

 

[Ackbach]

We will have something like that, right?

View attachment 3562

After that, why do we execute the commands [m] print(C->data)[/m] and [m]Pr(C->lc)[/m]?
If there were also other commands, after the command [m]Pr(P->lc)[/m], would they be executed for G or would the [m]G[/m] node be again fully processed? (Thinking)

It seems to me that the missing concept in your understanding is the idea of a stack. The basic idea of a stack is simple: last in, first out. That is, the last thing you put on the stack is the first thing you take off it. Think of one of those cafeteria tray stacks with the springs under them, or like what some restaurants have with springs underneath plates. "Pushing" is the act of putting something on the stack, and "popping" is the act of taking something off the stack. A stack is to be contrasted with a linked list, where the first thing you put in the last is the first thing you would take off the list (first in, first out).

Now then, when you call a function in a language, all sorts of things happen, but one thing that happens is that there is a place in the computer where the execution control is (what's going to be executed next). This is the "call stack". It tells you what will execute next.

When you use a recursive function like [m]Pr[/m], the call stack is absolutely essential to understanding what's going to happen next. I'm going to see if I can illustrate with a little table of execution here. The code will be on the left, and the stack will be on the right. The "top" of the stack will be to the right, and the Call Stack State will be what the call stack looks like after the corresponding code to the left finishes executing. Also, you have to keep track of which function instance is currently running, so I'll do that with dot notation. "Pr(A).statement" means that "statement" is executing in the "Pr(A)" instance.

[table="width: 700, align: left"]
[tr]
[td]Code Executing [/td]
[td]Call Stack State (top is to the right)[/td]
[/tr]
[tr]
[td]Pr(A)[/td]
[td]Pr(A) (pushing Pr(A) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(A).(A==NULL) False[/td]
[td]Pr(A)[/td]
[/tr]
[tr]
[td]Pr(A).Pr(C)[/td]
[td]Pr(A), Pr(C) (pushing Pr(C) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(C).(C==NULL) False[/td]
[td]Pr(A), Pr(C)[/td]
[/tr]
[tr]
[td]Pr(C).Pr(G)[/td]
[td]Pr(A),Pr(C),Pr(G) (pushing Pr(G) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(G).(G==NULL) False[/td]
[td]Pr(A), Pr(C),Pr(G)[/td]
[/tr]
[tr]
[td]Pr(G).Pr(G->rc) [/td]
[td]Pr(A),Pr(C),Pr(G),Pr(G->rc) (pushing Pr(G->rc) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(G->rc).(G->rc==NULL) True[/td]
[td]Pr(A),Pr(C),Pr(G),Pr(G->rc)[/td]
[/tr]
[tr]
[td]Pr(G->rc).return [/td]
[td]Pr(A),Pr(C),Pr(G) (popping Pr(G->rc) off the stack) [/td]
[/tr]
[tr]
[td]Pr(G).print(G->data) (42) [/td]
[td]Pr(A),Pr(C),Pr(G)[/td]
[/tr]
[tr]
[td]Pr(G).Pr(G->lc) [/td]
[td]Pr(A),Pr(C),Pr(G),Pr(G->lc) (pushing Pr(G->lc) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(G->lc).(G->lc==NULL) True[/td]
[td]Pr(A),Pr(C),Pr(G),Pr(G->lc)[/td]
[/tr]
[tr]
[td]Pr(G->lc).return[/td]
[td]Pr(A),Pr(C),Pr(G) (popping Pr(G->lc) off the stack)[/td]
[/tr]
[tr]
[td]Pr(G).} (end of routine) [/td]
[td]Pr(A),Pr(C) (popping Pr(G) off the stack)[/td]
[/tr]
[tr]
[td]Pr(C).print(C->data) (50) [/td]
[td]Pr(A),Pr(C)[/td]
[/tr]
[tr]
[td]Pr(C).Pr(F) [/td]
[td]Pr(A),Pr(C),Pr(F) (pushing Pr(F) onto the stack)[/td]
[/tr]
[tr]
[td]Pr(F).(F==NULL) False[/td]
[td]Pr(A),Pr(C),Pr(F)[/td]
[/tr]
[tr]
[td]Pr(F).Pr(F->rc) [/td]
[td]Pr(A),Pr(C),Pr(F),Pr(F->rc) (pushing Pr(F->rc) onto the stack)[/td]
[/tr]
[tr]
[td]etc.[/td]
[td][/td]
[/tr]
[/table]

Hopefully, if you have your latest version of your code, and the tree itself in front of you, and you compare this table of execution with those carefully, it will help you to see what's going on. Does this help?

You really have to have multiple levels of abstraction in your mind simultaneously in order to understand recursion.

 

[evinda]

I haven't understood why we finish with the node G and continue with the node C.. (Worried)
Because of the execution of [m]Pr(G->lc)=Pr(NULL)[/m] or because of the fact that there are no other commands after the command [m]Pr(G->lc)[/m] ?

 

[Ackbach]

I haven't understood why we finish with the node G and continue with the node C.. (Worried)
Because of the execution of [m]Pr(G->lc)=Pr(NULL)[/m] or because of the fact that there are no other commands after the command [m]Pr(G->lc)[/m] ?

The second. We process [m]Pr(G->lc)[/m], but that is a null pointer. Since we have processed the left child, and that's the last command in the recursive function, then [m]Pr(G)[/m] finishes executing, and gets popped off the call stack. This is represented in my table somewhat awkwardly by the [m]Pr(G).}[/m] line.