Explain call stack of this function?

  • Thread starter uestions
  • Start date
  • #1
22
0
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:

Answers and Replies

  • #2
12,089
5,768
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:
  • #3
jtbell
Mentor
15,635
3,682
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.
 
  • Like
Likes 1 person
  • #4
22
0
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.
 
  • #5
12,089
5,768
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
 
  • #6
22
0
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
 
  • #7
12,089
5,768
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...
 
  • Like
Likes 1 person
  • #8
22
0
1 more question, what makes the program return to calls recursion0(3) and (4) when nothing explicitly says to return there?
 
  • #9
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,899
174
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?
 
  • Like
Likes 1 person
  • #10
12,089
5,768
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.
 
  • Like
Likes 1 person
  • #11
12,089
5,768
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
 

Related Threads on Explain call stack of this function?

  • Last Post
Replies
19
Views
890
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
4
Views
37K
Replies
4
Views
9K
Replies
2
Views
2K
Replies
2
Views
5K
Replies
4
Views
3K
Replies
5
Views
824
Replies
4
Views
623
Top