Confused in understanding recursion

Question

I am little bit confused with the following code to find height of the tree and the code to find sum of n nos recursively, which is below this. What does the lheight and rheight store, depending on the number of recursions it makes?

int height(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
     lheight = height(node->left);
     rheight = height(node->right);
     if (lheight > rheight)
         return(lheight+1);
     else return(rheight+1);     
   }
}

Here is one more clarification, it prints the sum of n nos:

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = n + findSum(n-1);
    return sum;
}

if I change this to:

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = findSum(n-1); // here
    return sum;
}

It prints the output as 0. Why doesn't this return the number of recursions, if the above tree code does?

Did you have a look at http://stackoverflow.com/questions/717725/understanding-recursion?rq=1 — Pradheep, May 21 '13 at 08:06
Bro I can understand the recursion logic but I don understand how does the two variables above store the level of each sub-tree... — abu, May 21 '13 at 08:10
read the top answer and work the examples along with his explanation. Once you are done with the two this will become obvious — Pradheep, May 21 '13 at 08:14
yeah bro...I think u didn't understand me yet...I do understand the recusion but little bit confused with those two variables...plz read the comment I made `@Mohamed` and explain me.... — abu, May 21 '13 at 08:27

MOHAMED · Accepted Answer · 2013-05-21T08:43:52.140

3

Your second recursion is equivalent to

sum = findSum(n-1) = findSum(n-2) = findSum(n-3) = ..... = findSum(0) = 0;

If you want that the second recursion return the number of recursion then use

sum = 1 + findSum(n-1);

the lheight and rheight return the tree level because in the recursion function there is incrementation with 1 for both variables:

     return(lheight+1);
 else return(rheight+1);

If you want your findsum() do the samething as your height() recusrsion you should return sum+1 and not sum at the end of your findsum() function:

int findSum(int n){
    int sum;
    if(n <= 0) return 0;
    else sum = findSum(n-1);
    return sum+1; //<<<<< should return sum +1 as you did in the height function
}

the return sum+1; will be evaluated only if the

findSum(n-1); findSum(n-2); findSum(n-3); ...findSum(0); are called.

when findSum(0) is called, it will return 0;
when findSum(1) is called, it will execute sum=findSum(0) (so sum = 0) and then return sum+1 (1);
when findSum(2) is called, it will execute sum=findSum(1) (so sum = 1) and then return sum+1 (2);
when findSum(3) is called, it will execute sum=findSum(2) (so sum = 2) and then return sum+1 (3);
.
.
.
when findSum(n) is called, it will execute sum=findSum(n-1) (so sum = n-1) and then return sum+1 (n);

edited May 21 '13 at 08:43

answered May 21 '13 at 08:03

MOHAMED

41,599
58
163
268

Thank u for ur solution to find the no of recusion...Could u plz explain then how does the `lheight` and `rheight` outputs the level of tree correctly ??? – abu May 21 '13 at 08:07
@abu the `lheight` and `rheight` return the tree level because in the recursion function there is incrementation with `1` for both variables: – MOHAMED May 21 '13 at 08:16
@abu and in you recursion of `sum = findSum(n-1);` there is no incrementation with 1 – MOHAMED May 21 '13 at 08:17
k bro..if the level of the left sub-tree is 3 and it s the larger one, the value the lheight holds is 2 (before it returns by incrementing ) rit, I wanna u to clarify this (i.e) how does it store the value `2` whether it holds the no of recursions it made ??? – abu May 21 '13 at 08:21
oh yeah u got my point...what is the value of `sum` before it s returned..bcoz if I include a stmt `cout<<"\nSum : "< – abu May 21 '13 at 08:32

score 1 · Answer 2 · answered May 21 '13 at 08:07

1

I suggest you do this on paper. If we do it for the (unmodified) findSum function it will be like this:

Lest say you call it like

findSum(2);

This will read to the following steps:

1: sum = 2 + findSum(2 - 1);

Which will call findSum(1) which leads to

2: sum = 1 + findSum(1 - 1);

which calls findSum(0) which is

3: return 0;

Now we go back up one step to 2:

2: sum = 1 + 0;

and back up once more:

1: sum = 2 + 1

So the result of findSum(2) is 3.

answered May 21 '13 at 08:07

Some programmer dude

400,186
35
402
621

Thank u sir....but wat I wanna knw is how does the above two variables store the level of each sub-tree.... – abu May 21 '13 at 08:11
@abu Trace the function on paper for a small tree. Or even step through the code in a debugger for a small tree. It really helps. – Some programmer dude May 21 '13 at 08:13
@abu Maybe my answer could help you. Give it a try. – Kraken May 21 '13 at 08:15

score 1 · Answer 3 · answered May 21 '13 at 08:09

lheight and rheight are nothing but the heights of left subtree and right sub tree resp at a particular level of the Tree.

This can be made easier to understand if you take up an example. Tree

In the attached figure, we start off with root F. We check if the root is null, or not, and since it is not , we find the height of right subtree and left subtree, and whichever is more, we add one more to it and return. This is how we would do it manually.

Now while finding the height of left sub tree, we recursively go down, till we reach a null pointer, at which point we return 0. Hence the value return for A is 0, and then we check the height of right sub tree (i.e D) and for that we recursively go down till C, for which 0 is returned, and similarly 0 is returned for 0. We add one to the max of C and E (i.e 0) and return it to the upper level. Now we have value 0 for A and 1 for D, we add one to the max ( i.e. 1) and return it to the upper level. Which is the height of left subtree of the complete tree, similarly the height of right subtree is calculated.

Confused in understanding recursion

3 Answers3