Ralf Marmorglatt Ralf Marmorglatt - 8 months ago 38
Python Question

Python - does range() mutate variable values while in recursion?

While working on understanding string permutations and its implementation in python (regarding to this post) I stumbled upon something in a

for
loop using
range()
I just don't understand.

Take the following code:

def recursion(step=0):
print "Step I: {}".format(step)
for i in range(step, 2):
print "Step II: {}".format(step)
print "Value i: {}".format(i)

print "Call recursion"
print "\n-----------------\n"

recursion(step + 1)

recursion()


That gives the following output:

root@host:~# python range_test.py

Step I: 0
Step II: 0
Value i: 0
Call recursion

-----------------

Step I: 1
Step II: 1
Value i: 1
Call recursion

-----------------

Step I: 2
Step II: 0 <---- WHAT THE HECK?
Value i: 1
Call recursion

-----------------

Step I: 1
Step II: 1
Value i: 1
Call recursion

-----------------

Step I: 2
root@host:~#


As you can see the variable
step
gets a new value after a certain
for
loop run using
range()
- see the
WHAT THE HECK
mark.

Any ideas to lift the mist?

Answer Source

Your conclusion is incorrect. step value does not change by using range. This can be verified as:

def no_recursion(step=0):
    print "Step I: {}".format(step)
    for i in range(step, 2):
        print "Step II: {}".format(step)
        print "Value i: {}".format(i)

no_recursion(step=2)

which produces the output:

 Step I: 2

which is expected since range(2,2) returns [].

The illusion that step changes its value to 0 comes since the function recursion (called with step=2) returns after it prints Step I: 2, then control is returned to function recursion (called with step=1) which immediately returns since its for loop has terminated, and then control is returned to recursion (called with step=0) which continues since it has 1 iteration left, and that prints Step II: 0 to console which is no surprise. This can be simpler to observe if we modify the code a little bit (by adding function entry and exit logging) and observe the output:

def recursion(step=0):
    print "recursion called with [step = {}]".format(step) # add entry logging
    print "Step I: {}".format(step)
    for i in range(step, 2):
        print "Step II: {}".format(step)
        print "Value i: {}".format(i)

        print "Call recursion"
        print "\n-----------------\n"

        recursion(step + 1)
    print "--> returned recursion [step = {}]".format(step) # add exit logging 

recursion() 

the output produced by this code is :

recursion called with [step = 0]
Step I: 0
Step II: 0
Value i: 0
Call recursion

-----------------

recursion called with [step = 1]
Step I: 1
Step II: 1
Value i: 1
Call recursion

-----------------

recursion called with [step = 2]
Step I: 2
--> returned recursion [step = 2]
--> returned recursion [step = 1]
Step II: 0
Value i: 1
Call recursion

-----------------

recursion called with [step = 1]
Step I: 1
Step II: 1
Value i: 1
Call recursion

-----------------

recursion called with [step = 2]
Step I: 2
--> returned recursion [step = 2]
--> returned recursion [step = 1]
--> returned recursion [step = 0]

where we can clearly see that order in which recursion unfolds and observe that value of step is consistent in each step.