Leetcode Decode Ways问题递归深度超限错误排查求助

我正在求解LeetCode的Decode Ways问题，规则是大写英文字母对应数字：A=1，B=2……Z=26，给定一串数字字符串，求它可解码为字母字符串的方式数量。

比如字符串"11106"有两种有效解码方式：

• "AAJF"，对应分组(1 1 10 6)
• "KJF"，对应分组(11 10 6)

注意：分组(1 11 06)是无效的，因为06不能映射成F，06和6是不同的。

我用Python写的代码，哪怕是很短的输入都会触发最大递归深度错误，代码如下：

def numDecodings(s):

    ## Case of empty string 
    if len(s)== 0:
        return 1

    ## Error cases if a zero is in a weird place
    for idx, i in enumerate(s):
        if idx == 0 and s[idx]=="0":
            return 0
        if idx > 1 and s[idx-1] not in "12" and s[idx]==0:
            return 0

    ## Recursion
    def subProblem(substring):
        if len(substring) == 1:
            res = 1
        else:
            res = subProblem(substring[1:])
            if (len(substring) > 1) and (substring[0] == "1") or (substring[0] == "2" and (substring[1] in "0123456")):
                res += subProblem(substring[2:])
        return res
            
    return subProblem(s)

请问是什么原因导致了无界递归？

原因分析 #

• 递归终止条件不全：你的subProblem函数只处理了长度为1的子串，完全没考虑空字符串的情况。当递归到空字符串时，函数会进入else分支，继续调用subProblem(substring[1:])——空字符串切片后还是空，这就形成了无限递归循环，直接触发最大递归深度错误。

• 子问题的无效情况未处理：主函数里的零检查不完整，而且subProblem遇到长度为1的子串不管内容直接返回1。比如子串是"0"时，按照题目规则是无法解码的，但你的代码会返回1，这不仅逻辑错误，还会让递归在遇到这类子串时错误地继续执行，甚至加剧递归死循环的问题。

举个实际例子，输入"10"时：

1. 主函数检查不会触发返回，进入subProblem("10")；
2. 长度不是1，调用subProblem("0")，返回1；
3. 检查"10"符合两位有效编码的条件，调用subProblem("")；
4. 空字符串进入else分支，再次调用subProblem("")，无限循环下去，直到触发递归深度限制。

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