Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Explain call stack of this function?

  1. Dec 1, 2013 #1
    I have the code (space = _):

    def recursion0(x):
    ____if x == 1:
    ________return 1
    ____else:
    ________recursion0(x-1)
    ________print x

    I know values 2-x will print, but I cannot figure out how to map the call stack. Below are my thoughts.

    Let's set x = 3. 3 goes to 2 in recursion0(3-1), and then 2 goes to 1 in recursion0(2-1). Nothing is returned because there are no return statements, except for 1 which is the value given to recursion0(2). Then 2 is printed because x = 2. I still don't know what happens after this so 3 is printed. What happens after this so 3 is printed?
    Another question, why does x print after 1 is returned (and not before)?
     
    Last edited: Dec 1, 2013
  2. jcsd
  3. Dec 1, 2013 #2

    jedishrfu

    Staff: Mentor

    Basically your code is calling the function again and again until the argument is 1 and then it returns.

    You need to literally step thru your program line by line and when you hit the recursion0 function

    Code (Text):

    rec(4) start with x=4 as an example
    _x==1? no so we go to the else
    _rec(4-1) so we call recursion0 with arg =3
    __x==1? no so we go to the else
    __rec(3-1) so now we call recursion0 with arg=2
    ___x=1? no so we go to the else
    ___rec(2-1) ...
    ___print 2
    __print 3
    ...
     
    does it make sense now?

    One way to see this is to add a print stmt at the start of your function print: ">>> Entering recursion0 with x=", x

    and a print stmt at the end of your function: print ">>> Exitting recursion0 with x=", x
     
    Last edited: Dec 2, 2013
  4. Dec 1, 2013 #3

    jtbell

    User Avatar

    Staff: Mentor

    You can make the spaces display properly by enclosing your code between [noparse]
    Code (Text):
     and
    [/noparse] tags:

    Code (Text):

    def recursion0(x):
        if x == 1:
            return 1
        else:
            recursion0(x-1)
            print x
     
    Click the "Quote" button on this post to see exactly what I did.
     
  5. Dec 2, 2013 #4
    jedishrfu, what causes 3 to print when only 1 is returned to recursion0(2)? I am thinking since only a value is returned to recursion0(2), the function would stop there.
     
  6. Dec 2, 2013 #5

    jedishrfu

    Staff: Mentor

    Each time the ELSE block is executed the recursion0 function is called again before it can reach the print statement so in a sense the print statement execution is put on hold until that function returns.

    The value returned by your recusion0 function is not assigned to any variable and is not used anywhere in your program. Normally it would be as in the factorial recursion function shown below:

    Code (Text):

     def factor(x):
        if x==0
            return 1
        else:
            return x*factor(x-1)
     
    and you can see the action by adding extra print statements as shown below:

    Code (Text):


    def factor(x):
        print "Entering factor(", x, ")"
        if x==0:
            rc=1
        else:
           rc=x*factor(x-1)

        print "Exitting factor(", x, ") returning value: ",rc
        return rc

     
     
  7. Dec 2, 2013 #6
    So (for my code with x=4) does it flow like this:
    recursion0(4)
    x!= 1
    else recursion0(3)
    x != 1
    else recursion0(2)
    x!= 1
    else recursion0(1)
    x==1
    return 1 to recursion0(2)
    print 2
    Return to recursion0(3)
    print 3
    Return to recursion0(4)
    print 4
     
  8. Dec 2, 2013 #7

    jedishrfu

    Staff: Mentor

    Yes, does it make sense now? Recursion is a cool technique to learn, it develops very compact code which may use a little more computer resources than the equivalent for loop but is very elegant.

    Don't forget to thank people via the thanks button...
     
  9. Dec 2, 2013 #8
    1 more question, what makes the program return to calls recursion0(3) and (4) when nothing explicitly says to return there?
     
  10. Dec 2, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When a function call is finished it automatically jumps back to where the function was called, even if the function doesn't return anything. Consider the following two lines:

    arbitraryfunction(3)
    print(3)

    what could arbitraryfunction(3) possibly do to prevent print(3) from executing?
     
  11. Dec 2, 2013 #10

    jedishrfu

    Staff: Mentor

    Your code looks like python and by default it adds a return at the end of your function what it returns is undefined but is probably a zero.
     
  12. Dec 2, 2013 #11

    jedishrfu

    Staff: Mentor

    In rare cases, it could throw an exception which would bubble up until some block caught it.

    http://www.tutorialspoint.com/python/python_exceptions.htm
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Explain call stack of this function?
  1. C++ Function Calling (Replies: 7)

Loading...