Solving sAllPairs(4) Recursively - 14 Calls

[gfd43tg]

Homework Statement

Suppose you are given the recursion function sAllPairs, given as

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)?

Homework Equations

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.

 

[mfb]

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?

 

[gfd43tg]

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

 

[gfd43tg]

$\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.

 

[mfb]

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

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

$\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?

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.

 

[gfd43tg]

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

 

[mfb]

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

Why?

num = 0, 0 calls
num = 1, 2 calls

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?

 

[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.

 

[gfd43tg]

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

 

[gfd43tg]

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 isn't SAP a root, hence should come before 3 which is a child of SAP(3)??

 

[mfb]

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

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

 

[gfd43tg]

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 wouldn't 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.

 

[mfb]

It's a bit confusing that you include the integers, they are not function calls.
Instead of 4->3->2->..., it should start with SAP(4)->SAP(3)->SAP(2)->... which is always the call at the left side of the addition process.

 

[gfd43tg]

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

 

[gfd43tg]

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?

 

[rcgldr]

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

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:

    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.