использование массива python в рекурсивной функции вызывает потерю ссылки

Question

Я попытался решить вопрос рекурсивным способом, который известен как буквенные комбинации телефонного номера.

В этом вопросе телефонные номера сопоставляются с буквами, а для заданных цифр - с комбинациями букв.задаются соответствующие цифры.

dic = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z']
}

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Я пытался решить эту проблему с помощью функции рекурсии, но получил неожиданный вывод [""].

def telephoneHelper(digits, index, ans):
    if(index==len(digits)):
        return ans
    else:
        tmp=[]
        for letter in dic[digits[index]]:
            for an in ans:
                tmp.append(an+letter)
        ans=tmp
        telephoneHelper(digits, index+1, ans)

def telephoneNumberRec(digits):
    ans=[""]
    if(len(digits)!=0):
        telephoneHelper(digits, 0, ans)
    return ans

ans=telephoneNumberRec("23")
print(ans)

Я знаю, что есть много ответовсвязан с этой темой, но я пытаюсь понять проблему в этом коде.

Answer 1

combinations = []
def telephoneHelper(digits,index, ans):
    n = len(digits[0])
    for i in range(n):
        item = ans + digits[0][i]
        if (index==len(digits)):
            combinations.append(item)
        else:
            telephoneHelper(digits[1:],index+1, item)
    return(combinations)


def telephoneNumberRec(input_):
     a = []
     for letter in input_:
          a.append(dic[letter])
     return (telephoneHelper(a, 0, '')) # a = [['a', 'b', 'c'], ['d', 'e', 'f']]

print (telephoneNumberRec('23'))

выход:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Answer 2

Вам нужно добавить два оператора возврата (один в phoneNumberRec и один в функцию telephoneHelper), чтобы рекурсия действительно работала. Рабочий код будет выглядеть так:

dic = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z']
}
def telephoneHelper(digits, index, ans):
    if(index==len(digits)):
        return ans
    else:
        tmp=[]
        for letter in dic[digits[index]]:
            for an in ans:
                tmp.append(an+letter)
        ans=tmp
        return telephoneHelper(digits, index+1, ans)

def telephoneNumberRec(digits):
    ans=[""]
    if(len(digits)!=0):
        return telephoneHelper(digits, 0, ans)
    return ans

ans=telephoneNumberRec("23")
print(ans)