CODEWITHSUNDEEP
pythonlistrecursionpass-by-referencepass-by-value
SS'
SS'

Reputation: 857

Enumerating recursively with pass by reference in Python

So this is an answer to an interview problem, enumerate all possible mnemonics (possible character sequences given a phone number). Similar to a generate possible permutations problem and things of that sort so question applies there too.

MAPPING = ('0', '1', 'ABC', 'DEF', 'GHI', 'JKL', 'MNO', 'PQRS', 'TUV', 'WXYZ')


def phone_mnemonic(phone_number):
    def phone_mnemonic_helper(digit):
        if digit == len(phone_number):
            # All digits are processed, so add partial_mnemonic to mnemonics.
            # (We add a copy since subsequent calls modify partial_mnemonic.)
            mnemonics.append(''.join(partial_mnemonic))
        else:
            # Try all possible characters for this digit.
            for c in MAPPING[int(phone_number[digit])]:
                partial_mnemonic[digit] = c
                phone_mnemonic_helper(digit + 1)

    mnemonics, partial_mnemonic = [], [0] * len(phone_number)
    phone_mnemonic_helper(0)
    return mnemonics

I'm more confused at how this works with regards to pass by value/reference. Since 'partial_mnemonic' is declared at the bottom before the helper function is called and is modified within, in the recursion stack, aren't they operating on the same 'partial_mnemonic' object?

Because we're not passing in a list called 'partial_mnemonic' and simply using the one in the outer scope, why is it that we don't encounter problems modifying the same list?

Think I may be a bit confused on how Python works with regards to pass by value / reference but I'm not too sure why this code works using the same 'partial_mnemonic' list rather than instantiating a new one and passing that in when calling recursively.

Upvotes: 0

Views: 95

Answers (1)

J. Blackadar
J. Blackadar

Reputation: 1961

You are creating a new partial_mnemonic variable to hold your partial mnemonic recursively, before entering the recursive function. Once you enter the recursive helper function, the code builds mnemonics at each digit place by changing the value of partial_mnemonic at each digit, and calling recursively to keep building possibilities. Once a recursive trace of partial_mnemonic reaches the length of a phone number, the base case will append it to your list of permutations. The code will run through each possibility using the for loop, which calls the same method again, just with the partial_mnemonic list that now contains a partially built mnemonic. There is no reason to pass a new list in to the helper function as this would eliminate the recursive functionality.

Upvotes: 1

Related Questions