Ralf Marmorglatt Ralf Marmorglatt - 10 days ago 5
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

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.

Comments