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

Question

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?

`range(2, 2)` is empty. It doesn't enter the `for` loop. So it prints `Step I: 2`, then it returns, the previous function with `range(1, 2)` has then also completed its 1 iteration, so then you're back to where `step` was 0. — Aran-Fey, Sep 07 '16 at 06:10
[`itertools.permutations`](https://docs.python.org/2/library/itertools.html#itertools.permutations) — GingerPlusPlus, Sep 07 '16 at 06:12

Abhishek Kedia · Accepted Answer · 2016-11-24T08:04:55.233

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.

@RalfMarmorglatt glad that helped! – Abhishek Kedia Sep 08 '16 at 15:45 — Abhishek Kedia, Sep 08 '16 at 15:45

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

1 Answers1