how variables are stored and treated in recursion function in python?

Question

I am quite confused with the code below.

def a(x):
    print(x)    
    if x > 0:
        a(x - 1)
    print(x)    #I am confused with this print statement 

a(5)

The above code outputs:

Up till the 0 I understand how it prints, but then why it prints in ascending order.
Variable x is changing so what I thought the output would be is the last assigned value of x that is 0.
My predicted output:

So how does it track the value of x...?
Can someone explain in brief what actually happens in recursive functions and how variables are stored in it.

No variable x is not changing: each function call has its own x. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 13, 2017 at 13:35
This has nothing to do with the function being recursive. Calling a function with x - 1 does not alter the value of x in the current scope. You may find pythontutor.com useful. — jonrsharpe
– jonrsharpe, Commented Feb 13, 2017 at 13:37
Seems like you should read a little about the stack, for example here: cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/stack.html - this is how functions store their local variables, return values, etc. — Yotam Salmon
– Yotam Salmon, Commented Feb 13, 2017 at 13:37

willeM_ Van Onsem · Accepted Answer · 2017-02-13 13:38:24Z

11

You have to understand that for each function call the x is local. So it means that the second call to f has a different x. To visualize this: you can see it like:

f(x=5)
    print(x) # this x = 5
    f(x=4)
        print(x) # this x = 4
        f(x=3)
            print(x) # this x = 3
            f(x=2)
                print(x) # this x = 2
                f(x=1)
                    print(x) # this x = 1
                    f(x=0)
                        print(x) # this x = 0
                        print(x) # this x = 0
                    print(x) # this x = 1
                print(x) # this x = 2
            print(x) # this x = 3
        print(x) # this x = 4
    print(x) # this x = 5

So in your recursive calls, there are six xes. Each of the x variables can have a different value and changing them one level deeper has no impact on the level above, etc.

answered Feb 13, 2017 at 13:38

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

WhatsThePoint Over a year ago

Comments

Alfe · Accepted Answer · 2017-02-13 13:41:38Z

3

Calling a(5) will start function a() with x = 5. This will do three things:

First print x (which is of value 5)
Then call a(4)
Then (after everything else) print x again (which is still of value 5).

Step 2 just happens to be a bit elaborate, because it also will do these three steps (print "4" twice and call a(3) in between). This will go down until a(0) is called which will only print 0 twice but not call a() again.

answered Feb 13, 2017 at 13:41

Alfe

60.2k21 gold badges117 silver badges172 bronze badges

Comments

hfz · Accepted Answer · 2017-02-13 13:54:27Z

Let me try to explain. a(4),a(3),a(2) and a(1) are called recursively as they fall in the if statement so in the stack, a(5) is at the bottom and a(1) is on top ,since they are stacked bottom up

def a(x):
    print(x) # executed    
    if x > 0:
        a(x - 1) #executed
    print(x)

Result: 5,4,3,2,1

When a(0) is called,it doesn't fall into the if statement hence it prints 0 twice. ONLY a(0) is executed to completion,a(1) to a(5) haven't finished executing yet since they are still in the stack.

def a(x):
    print(x)    #executed
    if x > 0:
        a(x - 1)
    print(x)    #executed

Result: 0 , 0

How do we finish executing these function calls? We have to pop them off the stack. Recall i mentioned a(5) is on the bottom and a(1) is on top. Stacks are popped top down hence when a(0) returns, it calls a(1) and a(1) finishes executing its last statement. After a(1) is popped, a(2) is then called and so on.

def a(x):
    print(x)    
    if x > 0:
        a(x - 1)
    print(x)    #executed

Result: 1,2,3,4,5

The stack is now fully popped.

secureamd2 · Accepted Answer · 2017-02-13 13:59:16Z

2

This is related to stack.
for every call a different x is created and so the value of x gets prints in the ascending order.

answered Feb 13, 2017 at 13:59

secureamd2

1037 bronze badges

Collectives™ on Stack Overflow

how variables are stored and treated in recursion function in python?

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related