# Explain call stack of this function?

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:

Related Programming and Computer Science News on Phys.org
jedishrfu
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:
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:
jtbell
Mentor
I have the code (space = _):
You can make the spaces display properly by enclosing your code between [noparse]
Code:
 and
[/noparse] tags:

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

• 1 person
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
Mentor
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:

Code:
 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:
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

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
print 3
print 4

jedishrfu
Mentor
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
print 3
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...

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

Office_Shredder
Staff Emeritus
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?

• 1 person
jedishrfu
Mentor
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.

• 1 person
jedishrfu
Mentor
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