1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive calls

  1. Aug 9, 2014 #1

    Maylis

    User Avatar
    Gold Member

    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.
    ImageUploadedByPhysics Forums1407569013.095024.jpg
     
  2. jcsd
  3. Aug 9, 2014 #2

    mfb

    User Avatar
    2016 Award

    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?
     
  4. Aug 9, 2014 #3

    Maylis

    User Avatar
    Gold Member

    Is my tree correct? I have doubts that the root would be sAllPairs(0)
     
  5. Aug 9, 2014 #4

    Maylis

    User Avatar
    Gold Member

    ##\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
  6. Aug 9, 2014 #5

    mfb

    User Avatar
    2016 Award

    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.
     
  7. Aug 9, 2014 #6

    Maylis

    User Avatar
    Gold Member

    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
     
  8. Aug 9, 2014 #7

    mfb

    User Avatar
    2016 Award

    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?
     
  9. Aug 9, 2014 #8

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Aug 9, 2014 #9

    Maylis

    User Avatar
    Gold Member

    ImageUploadedByPhysics Forums1407622436.891085.jpg

    I calculate 14 calls for num=4, and 8 calls for num=3
     
  11. Aug 9, 2014 #10

    Maylis

    User Avatar
    Gold Member

    ImageUploadedByPhysics Forums1407623530.644436.jpg

    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
  12. Aug 9, 2014 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I agree.
    You get the same number just by counting all function nodes in your tree apart from the top one.
     
  13. Aug 9, 2014 #12

    Maylis

    User Avatar
    Gold Member

    ImageUploadedByPhysics Forums1407624144.330818.jpg

    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.
     
  14. Aug 9, 2014 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  15. Aug 9, 2014 #14

    Maylis

    User Avatar
    Gold Member

    So in a tree, only function calls should be present??
     
  16. Aug 9, 2014 #15

    Maylis

    User Avatar
    Gold Member

    ImageUploadedByPhysics Forums1407626065.343959.jpg

    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?
     
  17. Aug 9, 2014 #16

    rcgldr

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Recursive calls
  1. Recursive function (Replies: 16)

  2. Recursion Tree (Replies: 3)

Loading...