How divide and conquer algorithms are implemented

[sherkhan]

Hi,
I was studying recursion in c++ recently. Although I understood the simple single-recursion as calculating factorial, etc, easily, but was unable to understand double or multiple recursion as in case of binary search, merge sort, binary search tree 's insert,inorder,preorder functions. I just couldn't get how programmer thought of using recursion in first place and how they guaranteed its success. To concentrate on topic I choose only this simple example of printing elements of binary search tree in inorder:

void inorder(node *temp){
          if(temp!=NULL){
               inorder(temp->left);
               cout << temp->data << " ";
               inorder(temp->right);
          }

Now precisely I can't understand two things:
1.How programmer thought in which order and what next case he should take for recursion.
2.How he guarantees that it will always print element in correct order.

Please help me in understanding these two issues. Thanks in advance and please forgive me if this post in wrong section( I posted here as I am a newbie in C++).

[jsmith]

Divide and conquer algorithms can be implemented using recursion.

In both cases, the idea is that a large problem can be solved by breaking it down
into smaller, but identical problems. This means that the same algorithm can
be used to solve the smaller problems as the larger.

In-order traversal means that you first visit the left child, then visit the "current" aka
"parent" node, then visit the right child. What if the left child itself has children? It's
the same problem, only on a smaller part of the tree.

[sherkhan]

Thanks for reply jsmith!
Its quite clear to me now. Thanks for your short and simple reply.
Can you just do one more favour. How same thing applies for 'merge sort' also.
The divide part is clear but how every piece joins afterwards is still unclear to me!

[jsmith]

Check out:
http://en.wikipedia.org/wiki/Merge_sort