recursion

[dschwart]

Do you understand recursion? Would you like to help me understand recursion?
I have 3 questions about this procedure:

void Show_Tree(node * ptr_to_tree) {
   
   /*
   if (ptr_to_tree == 0) {
      printf("The tree is empty.\n\n");
      return;
   }
   */
   
   if (ptr_to_tree == 0)
      return;
   

   Show_Tree(ptr_to_tree -> ptr_to_left);
   printf("%d\n", ptr_to_tree -> i);
   Show_Tree(ptr_to_tree -> ptr_to_right);   
}

1. Why is this necessary, and what does it do?

if (ptr_to_tree == 0)
   return;

2. When I added an output instruction,

if (ptr_to_tree == 0) {
   printf("The tree is empty.\n\n");
   return;
}

I saw that the printf was called before every output statement that showed a node value. If your answer to question 1 did not explain that behavior, can you explain it now?

3. The part of the procedure that does the useful work looks like:

Show_Tree(ptr_to_tree -> ptr_to_left);
printf("%d\n", ptr_to_tree -> i);
Show_Tree(ptr_to_tree -> ptr_to_right);  

Why do I only need one printf? Why does the printf work for nodes on the right side of the tree?
Thank you very much for reading this far, and I hope you can take the time to answer my questions. It will help me a lot.

[oGN8b7Xj]

1. if ptr_to_tree == 0, means that there is no memory allocated in that pointer, and so, no tree at all.

2. Well, yes, the tree node is empty. What do you want to output anyway?

3. It will printf for the node you are in, and, when Show_tree, printf for the left and then printf for the right, until ptr_to_tree == 0, so no more tree.

Say:
1
/ \
2 3

ptr_to_tree->i = 1
ptr_to_tree->ptr_to_left = 2
ptr_to_tree->ptr_to_right = 3

For 2 and 3, ptr_to_tree == 0, so no printf neither left or right.

The output should be:
1
2
3

[YFGHNG]

Pointing to memory location 0 doesn't necessarily mean that there's no memory allocated to that pointer; however, since memory location 0 is used for important system stuff, like an interrupt table. It also depends on your OS. In most cases, the compiler and the system just won't let you access memory location 0, so having ptr_to_tree == 0; means it'll just be seen as a dead end. A stop mechanism.

http://stackoverflow.com/questions/2960496/why-is-null-0-an-illegal-memory-location-for-an-object

The rest is as @lechuga2000 mentioned already.

Also for recursion, it helps if you think if it as an Ouroboros snake eating itself. There has to be a point where it stops, and that's where your first question came in. Another thing is that, recursion is when a function calls itself, so for your third question, the Show_Tree checks for the end condition, and if it's not met, runs once for the left child, then runs once for the right child.