递归实现电话号码转助记符函数返回null问题求助

问题描述 #

给定非零长度的字符串格式电话号码，编写递归函数返回该号码的所有助记符。编写的代码在输入“1905”时，函数返回null，但在return语句前打印Mnemonics能得到正确结果，询问原因及解决方法。

原代码 #

def phoneNumberMnemonics(phoneNumber, Mnemonics=[''], idx=0):
    number_lookup={'0':['0'], '1':['1'], '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']}

    if idx==len(phoneNumber):
        return Mnemonics
    else:
        new_Mnemonics=[]
        for letter in number_lookup[phoneNumber[idx]]:
            for mnemonic in Mnemonics:
                new_Mnemonics.append(mnemonic+letter)
        phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)

问题原因 #

递归调用时，你只执行了phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)，但没有返回这个递归调用的结果。当递归进入最后一层（idx==len(phoneNumber)），虽然返回了正确的Mnemonics列表，但这个结果没有被上层函数传递回来，上层函数执行完递归调用后没有返回值，默认返回None（也就是你看到的null）。

修改方案 #

在else分支的递归调用前加上return，让每一层递归都把下层的结果传递回来：

def phoneNumberMnemonics(phoneNumber, Mnemonics=[''], idx=0):
    number_lookup={'0':['0'], '1':['1'], '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']}

    if idx==len(phoneNumber):
        return Mnemonics
    else:
        new_Mnemonics=[]
        for letter in number_lookup[phoneNumber[idx]]:
            for mnemonic in Mnemonics:
                new_Mnemonics.append(mnemonic+letter)
        # 加上return，传递递归结果
        return phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)

额外优化提示 #

默认参数Mnemonics=['']是可变对象，多次调用函数时可能会出现意外的累积问题（比如第一次调用后，默认列表会保留之前的结果）。更安全的写法是把默认参数设为None，在函数内部初始化：

def phoneNumberMnemonics(phoneNumber, Mnemonics=None, idx=0):
    number_lookup={'0':['0'], '1':['1'], '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']}
    
    if Mnemonics is None:
        Mnemonics = ['']

    if idx==len(phoneNumber):
        return Mnemonics
    else:
        new_Mnemonics=[]
        for letter in number_lookup[phoneNumber[idx]]:
            for mnemonic in Mnemonics:
                new_Mnemonics.append(mnemonic+letter)
        return phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)

内容的提问来源于stack exchange，提问作者trying2learn