# Recursive calls

1. Aug 9, 2014

### Maylis

1. The problem statement, all variables and given/known data
Suppose you are given the recursion function sAllPairs, given as
Code (Text):
function output = sAllPairs(num)
if num > 0
output = num + sAllPairs(num-1) + sAllPairs(num-2);
else
output = 0;
end
a) what is the output of the command sAllPairs(4)?

b) How many recursive calls are made when issuing the command sAllPairs(4)?

2. Relevant equations

3. The attempt at a solution
I was able to calculate on paper and confirm that the answer is 14 for part (a), but I am confused once again about how to traverse the tree. I know for pre-order traversal you process the root, then the subtree from left to right. However, after I process the root, I get to the left subtree, and it's sibling is a root to another subtree. So when that happens, I am uncertain how to traverse through this thing.

2. Aug 9, 2014

### Staff: Mentor

I would start from num=0:
How many function calls does sAllPairs(0) produce?
Based on that result, how many function calls does sAllPairs(1) produce?
[...]
Based on that result, how many function calls does sAllPairs(4) produce?

3. Aug 9, 2014

### Maylis

Is my tree correct? I have doubts that the root would be sAllPairs(0)

4. Aug 9, 2014

### Maylis

$\bullet$ So for num = 0, 0 + sAllPairs(-1) + sAllPairs(-2) = 0, it would make 0 recursive calls.

$\bullet$ num = 1, you get 1 + sAllpairs(0) + sAllPairs(-1). Thus, 1+0+0. Does that mean it took no recursive calls, since it already knows that the last two are equal to zero due to the else condition?

$\bullet$ Then for num = 2, 2 + sAllPairs(1) + sAllPairs(0), so 2+1+0. So it makes 1 recursive call

$\bullet$ num = 3, 3 + sAllPairs(2) + sAllPairs(1), so 3+3+1 = 7. It makes 2 recursive calls

$\bullet$ Finally, num = 4, 4+ sAllPairs(3) + sAllPairs(2), 4+7+3 = 14. It makes 2 recursive calls

for a total of 2+2+1 = 5 calls. I don''t know if this is the proper way to count calls though. If I am supposed to count any time I see sAllPairs for a num, then it would be 2 + 2 + 2 + 2 + 2 = 10, I just don't understand how one should count.

Last edited: Aug 9, 2014
5. Aug 9, 2014

### Staff: Mentor

Be careful, you don't even make this calculation.

You do call those sAllpairs functions here, so you get two calls.
Hmm, the list should start with -1 instead of 0, but -1 gives the same result as 0.

The numerical answer here does not matter, count the function calls instead of the function results. Calling a function that makes another 2 function calls gives 3 calls, for example.

6. Aug 9, 2014

### Maylis

My bad for the num = 0 case, I knew better than that!

But I am still confused for num = 1:4

They should all make 2 calls, thus a total of 8 calls, no?

num = 0, 0 calls
num = 1, 2 calls
num = 2, 2 calls
num = 3, 2 calls
num = 4, 2 calls

7. Aug 9, 2014

### Staff: Mentor

Why?
Okay.
num = 2:
The calculation is "output = num + sAllPairs(num-1) + sAllPairs(num-2);"
Plugging in num we get:
"output = num + sAllPairs(1) + sAllPairs(0);"
So we 1 call sAllPairs(1) which then makes 2 more calls, and we 1 call sAllPairs(0)which then makes 0 more calls, for a total of 1+2+1+0=4 recursive calls.

Can you work out 3 and 4?

8. Aug 9, 2014

### AlephZero

You can get the computer to check your counting. Print out the value of "num" each time you call the function. Put the print statement right at the start of the function before it has done anything. Then figure out what happened from the output you get.

This is a good strategy for making sure you understand any new concept in computer programming. The computer is an ideal teacher. It never makes mistakes, and it never loses patience. Knowing how to "ask the computer the right sort of questions to find out what is going on" is a valuable skill to learn.

9. Aug 9, 2014

### Maylis

I calculate 14 calls for num=4, and 8 calls for num=3

10. Aug 9, 2014

### Maylis

I wrote up the tree and if you count all the children for a given SAP(num), I found 8 and 14 for SAP(3) and SAP(4), respectively. Now, my question is, how is it traversing this tree?

The rule for pre-order traversal is process root, then subtree from left to right. So I start at SAP(4), then go to 4. Where I'm stuck is understanding whether it will go to 3, or will it go to SAP(3).

I am checking how the code works and I see it goes to 3, but I am confused as to why. If the rule is process root, then process subtree left to right, well isnt SAP a root, hence should come before 3 which is a child of SAP(3)??

Last edited: Aug 9, 2014
11. Aug 9, 2014

### Staff: Mentor

I agree.
You get the same number just by counting all function nodes in your tree apart from the top one.

12. Aug 9, 2014

### Maylis

I ran the function and got this as the traversal. I think where I am tripping up is some confusion over where it will go. So it will go from the root and get all the left subtrees that it can, which goes all the way down to 1, then it will go to SAP(0), SAP(-1), then finally connect with another root at SAP(1). But then after SAP(1), it goes up to SAP(2), instead of 1. I could see that if it didn't process that root it wouldnt ever have an opportunity to come back to it, but I guess it seems inconsistent that it would process that rooti nstead of the left subtree.

13. Aug 9, 2014

### Staff: Mentor

It's a bit confusing that you include the integers, they are not function calls.

14. Aug 9, 2014

### Maylis

So in a tree, only function calls should be present??

15. Aug 9, 2014

### Maylis

So can the tree traverse the same node twice? I am looking at the bottom left of the tree, specifically at the bottom SAP(0). It can either go back up to SAP(2), then over to SAP(1), or SAP(0) -> SAP(1) which I wrote, or SAP(0) to SAP(0). Which way would it go?

16. Aug 9, 2014

### rcgldr

You can have the program count the number of calls, just declare a static counts, such as:

Code (Text):

static int callcount;  /* initialiized to zero */

Do not explicity initialize the count, as it would get reset on each call.

Then for the first line of the recursive function increment the count:

Code (Text):

callcount ++;

Another issue here is that your trying to create a tree which has a mix of local values and either calls or returned values. A call stack would be a better diagram.