0

I am not able to understand the recursion of functions. How it works? how the values are stored and all? 

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    return(tree_size(node->left) + tree_size(node->right) + 1); 
  } 
}
dilara
  • 19
  • 10
user1553924
  • 31
  • 2
  • 1
    The values are generally stored on stack. You can think of taking a scratch paper, write something on it, put it away, do other thing, take the scratch paper back and continue work on it. It is somewhat the same. – nhahtdh Jul 26 '12 at 08:22
  • 6
    recursion: see recursion. (Sorry.) – podiluska Jul 26 '12 at 08:22
  • 1
    Very similar to: http://stackoverflow.com/questions/5631447/how-recursion-works-in-c/5631611#5631611 – forsvarir Jul 26 '12 at 08:37
  • It's all about stack unwinding! – Benny Jul 26 '12 at 08:58
  • @forsvarir I don't think this question is really about the recursion involved, I think it is more about the order the return line is executed – thecoshman Jul 26 '12 at 08:59
  • @thecoshman: I think you *could* interpret the question that way, but ordering isn't explicitly mentioned. The refers to not understanding recursion, how it works, or how values are stored. I'm not saying it's a duplicate of the other question, just that there's some overlap. As it stands, this question is probably bordering on being too broad as it's not clear what the OPs specific problem is. – forsvarir Jul 26 '12 at 09:08
  • @forsvarir true... I seem to have some how read something completely random from this question, which kinds of makes my answer seem rather stupid... – thecoshman Jul 26 '12 at 09:13
  • Try learning on fibonacci recursive example. Just look on Google for that. – A_nto2 Jul 26 '12 at 09:29
  • if any of the answers helped you enough, it is customary to accept one. If you still have questions, ask. Wasn't the metaphor with the two stacks of paper sheets in my answer clear enough? Do you need more clarifications? – Will Ness Aug 06 '12 at 00:24

4 Answers4

2

When entering a function, a new stack frame is created (on the stack in memory). The stack frame keeps track of the local data within that function, such as locally defined variables and incoming arguments. (And other things such as return address and previously stored register values that must be preserved. However this is not as relevant for this question.)

With recursion, when you call a function from within the same function , you create a new stack frame (as with any call), and that new stack frame will store the local variables for the new call.

As C. Stoll pointed out, the order of the two calls is unspecified, due to the + operator.

Man of One Way
  • 3,904
  • 1
  • 26
  • 41
  • 4
    Keep track of all data is a bit broad. It keeps track of the return address, the old stack frame pointer, the values in the register, the arguments to the function, and the local variables. – nhahtdh Jul 26 '12 at 08:25
  • well that helpped ! thank you... So the values are stored onto the stuck until a terminating condition and then they are retrieved in the order from up to down, the upper values returns the value to its next lower?? also in the above case, i have tree_size(node->left) + tree_size(node->right) , will these run in parallel with two stacks ? – user1553924 Jul 26 '12 at 08:31
  • They will not run in parallel. First tree_size(node->left) will be called (and all of its children). Then tree_size(node->right) will be called (and all of its children). They all use the same stack. – Man of One Way Jul 26 '12 at 08:34
  • 1
    @nhahtdh Yes, "all data within the function" was a bad definition. I've changed it now. – Man of One Way Jul 26 '12 at 08:35
  • No, the two function calls will be handled seperately and the values they return are stored in some temporary variable. The function calls itself one time, stores the result of this call somewhere, then calls itself a second time, adds the result to the stored value and finally returns this value (note: afaik it's not specified which call goes first). – C. Stoll Jul 26 '12 at 08:41
0

consider the follow three

     1
  2     3
 4 5   6
7

1 has two children (2 and 3) 2 has two children (4 and 5) .. 4 has one child (7)
and you want to know the size of the tree at 1: 

tree_size(tree1);

because tree1 is not NULL the if-condition not true, so the else statement will be executed:

tree_size(tree1): return tree_size( tree_size(tree2) + tree_size(tree3) + 1 )

same for tree2 and tree3

tree_size(tree2): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 )
tree_size(tree3): return tree_size( tree_size(tree6) + tree_size(NULL) + 1 )

and so on. Now if we substituate the return value of tree_size(tree2) and tree_size(tree3) in tree_size(tree1) we would get:

tree_size(tree1): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 + tree_size(tree6) + tree_size(NULL) + 1 + 1 )

Now you can see the term 1+1+1, this is the size of the tree for the first two niveau's, if we keep substituating the tree_size calls, w'll get an some of n times 1, with n the size of the tree

Joris W
  • 517
  • 3
  • 16
0

I think the line that is confusing you most is..

return(tree_size(node->left) + tree_size(node->right) + 1);

If you called this function on the top node, it will tell you that the number of nodes in the tree is the number of nodes to the left, plus the number to the right, plus this on node you just called the function on.

Now, I don't think it's the recursion that is confusing you, if it is, leave a comment and I can explain that a bit more.

The problem I think you are having is what order the line will be executed. Well, it follows the logical maths rules for 'addition'. Note, we know we do not have to get concerned with operator overloads, as tree_size is returning an int, so we have

intA + intB + intC;

I trust I do not need to tell you that it does not matter what order you add these three values, you will get the same result.

however, the order that these are added is well defined. If you think of the + operator as it's function, it will be a bit clearer. We basically have (and I hope I get this right):

operator+(intA , operator+( intB, intC);

so, you can see, we need to first calculate B + C before we can add on A, or if we take this back to the line of code in question, we get the tree_size on the right first, add one to it, then add on the tree_size of the left. This is an important thing to be aware of, you could do something very strange, such as edit the tree size when you get the value... say, if you moved nodes from one side to the other. Of course, it would be a very bad tree if getting the size of it was not something you can rely on.

I fear I might have gone on a bit too much here, so if I have missed the mark a bit, just leave a comment and I will gladly try to help improve this answer for you.

thecoshman
  • 8,394
  • 8
  • 55
  • 77
0

The analogy with using pieces of paper (by @nhahtdh in the comments to Q) is very good. Let me elaborate on it.

First, re-write your code in more linear manner:

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    x = tree_size(node->left);
    y = tree_size(node->right);
    z = x + y;
    r = z + 1;
    return( r ); 
  } 
}

Imagine you have a thick (practically inexhaustible) stack of empty sheets of paper in front of you. You also have various recipes (function definitions) to the left of you on your desk, and an empty space to the right of you.

Now, to call a function means to copy its definition from its recipe onto the sheet of paper on top of the stack of papers in front of you, then substitute the argument values of the call for the function parameters, and go on from there.

When you hit a line with a function call on it (any function call), mark that line on the sheet of paper in front of you, move that paper to your right (faced up), and start working on the new empty sheet of paper in front of you. Copy onto it the recipe for the function that you need to call, write down the argument values, and continue working on it according to the recipe now in front of you.

If you encounter another function call, repeat this sequence of actions: mark the line that needs to receive the result of the function call, put your current sheet of paper on top the pile to your right (facing up), copy the new recipe on the top sheet of paper in front of you, and go on from there as before.

Now when you hit a line in the current recipe that says return, write down the returned value onto the top sheet of paper in the pile to your right on the marked line there, then discard the current piece of paper in front of you and move back the top piece of paper from the stack of papers to you right onto the stack of papers in front of you.

That's it. All you needed were the two stacks of sheets of paper, one in front of you, and another one to your right, and the pile of papers with functions' definitions written on them, to your left.

Notice, we don't care if the function that we call is the same as one of the previous function calls that we performed, or not. It works just the same.

Will Ness
  • 70,110
  • 9
  • 98
  • 181