Explain call stack of this function?

[uestions]

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

 

[jedishrfu]

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

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

 

[jtbell]

I have the code (space = _):

You can make the spaces display properly by enclosing your code between [noparse]

 and

[/noparse] tags:

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.

 

[uestions]

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.

 

[jedishrfu]

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.

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:

 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:

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

 

[uestions]

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

 

[jedishrfu]

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

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

 

[uestions]

1 more question, what makes the program return to calls recursion0(3) and (4) when nothing explicitly says to return there?

 

[Office_Shredder]

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?

 

[jedishrfu]

1 more question, what makes the program return to calls recursion0(3) and (4) when nothing explicitly says to return there?

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.

 

[jedishrfu]

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?

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