Recursion ( Tool for Lazy Developer)

Lets take an example : find the sum all the n elements in an int array A.

Now I ask a very simple question to A, Can you please tell me the
sum of all the elements inside you?

A says, of course yes..

int contractor=0;
for(int i = 0; i < n; ++i )
contractor += i;

What did A do here?
A actually hired a contractor who goes to each of A's element, collects the data and sums it up.

Another day A was asked the same question.
Since he was feeling lazy to hire the contractor he just hands over this task to A1. A1 too being lazy announces that I don't know the solution but if A2 can give me the sum of elements from A2 to An, I can solve it, so A1 reduces the size of the problem and hands it over to A2. A2, A3,..they all did the same thing. finally when An-1 asks the same problem to An, An realizes that he knows the solution of sum of all elements from An onwards because there is no-one beyond An, so An just returns its value as the solution to An-1. during return, An-1, An-2, An-3...they all adds up their value to the solution and returns the final sum to the caller. This way, A will get the solution without hiring the contractor, because everyone did their own part of work in solving the problem.

Don't ever worry about writing the complete solution of the recursive problem. Don't be scared of it, Recursion in the simplest thing in the world. Here are the important steps for solving recursive problems.

1. Every recursive problem statement is a question asked to some object. Think about how to user of your application is going to use your function i.e
height(root) ==> what is the height ? asked to the root pointer of the tree.
factorial(n) ==> what is the factorial ? asked to an Integer n.
preOrder(root) ==> what is the pre-order? asked to the root pointer of the tree.

2. If the object doesn't know the exact solution to the question it assumes that it knows someone who can solve the problem of size N-1 and then it just works on their result to build the final solution.

3. If the object knows the exact solution to the question asked, it simply returns the solution to the caller.


Example: Is there any path in a binary tree whose path sum is S. =>doesSumExist(S, root);

Step 1: question is "Is there any path you know whose sum is S?" object here is root.

Step 2: since root in itself doesn't know the answer and root->left and root->right are the only guys it know of, so it announces that "If root->left and root->right both can answer my question "Is there any path you know whose sum is (S - value)" then I can solve the actual problem which was asked to me".

Step 3: when the question percolated down to leaf nodes of the tree, they knew the answer so they responded in "yes" or "no".

so code goes like..

bool doesSumExist(int S, Node *root)
{
if(root==NULL)
return FALSE;
if(root->left == NULL && root->right == NULL)
return S==root->value;
else
return doesSumExist(S -- root->value, root->left) ||
doesSumExist(S - root->value, root->right);
}

Conclusion : Try to be as lazy as possible when you take a recursive approach and rely completely on your neighbors for the solution. If you know the solution just return it otherwise just perform the additional calculation on top of what your neighbor returns in order to solve the problem.