Recursion: Index not updating

I am trying to find pairings in the variable ‘coordKeys’ down to the element level.

coordKeys = [0,1,2,3,4]

pairingDict = {}
index = 1
def scheduler(coordKeys, pairingDict, index):
    length = len(coordKeys)
    if length == 1:
        return 
    
    dividerInd = math.ceil(length/2)
    firstHalf = coordKeys[:dividerInd]
    secondHalf = coordKeys[dividerInd:]
    
    pairingDict[index] = (firstHalf, secondHalf)
    index += 1

    print(pairingDict)    
    scheduler(firstHalf, pairingDict, index)
    print(pairingDict)
    scheduler(secondHalf, pairingDict, index)
    print(pairingDict)
    return pairingDict

result = scheduler(coordKeys, pairingDict, index)
print(result)
Output:
{1: ([0, 1, 2], [3, 4])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([3], [4]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([3], [4]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([3], [4]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([3], [4]), 3: ([0], [1])}
{1: ([0, 1, 2], [3, 4]), 2: ([3], [4]), 3: ([0], [1])}

What I want in the output’s last line:

{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1]), 4:([3], [4])}

Can’t figure out why the value of ‘index’ variable is not staying put at 4. Please help on why calling ‘scheduler’ function on the [3],[4] part is thinking that index’s value is 2.

Answer

Integers are immutable. When you perform index += 1 it actually assigns to the local variable index a new integer object instead of mutating the original, so when the recursive calls return, the local variable index in the parent frame retains the reference to the original integer object, resulting your ([3], [4]) getting assigned to the key 2, the value of index at that level of the recursion.

To work around it, you can either make index a mutable list containing an integer instead:

import math

coordKeys = [0, 1, 2, 3, 4]

pairingDict = {}
index = [1]

def scheduler(coordKeys, pairingDict, index):
    length = len(coordKeys)
    if length == 1:
        return

    dividerInd = math.ceil(length / 2)
    firstHalf = coordKeys[:dividerInd]
    secondHalf = coordKeys[dividerInd:]

    pairingDict[index[0]] = (firstHalf, secondHalf)
    index[0] += 1

    print(pairingDict)
    scheduler(firstHalf, pairingDict, index)
    print(pairingDict)
    scheduler(secondHalf, pairingDict, index)
    print(pairingDict)
    return pairingDict


result = scheduler(coordKeys, pairingDict, index)
print(result)

or you can simply use the length of pairingDict plus 1 as the index:

import math

coordKeys = [0, 1, 2, 3, 4]

pairingDict = {}

def scheduler(coordKeys, pairingDict):
    length = len(coordKeys)
    if length == 1:
        return

    dividerInd = math.ceil(length / 2)
    firstHalf = coordKeys[:dividerInd]
    secondHalf = coordKeys[dividerInd:]

    pairingDict[len(pairingDict) + 1] = (firstHalf, secondHalf)

    print(pairingDict)
    scheduler(firstHalf, pairingDict)
    print(pairingDict)
    scheduler(secondHalf, pairingDict)
    print(pairingDict)
    return pairingDict


result = scheduler(coordKeys, pairingDict)
print(result)

Both would output the following in the last line:

{1: ([0, 1, 2], [3, 4]), 2: ([0, 1], [2]), 3: ([0], [1]), 4: ([3], [4])}

Leave a Reply

Your email address will not be published. Required fields are marked *