python - 将求值表达式传递给 Python 中的递归时出现问题

Question

这个问题我遇到过很多次了。示例递归的思想是通过从输入数组中选择每个元素的一个字符来生成所有字符组合。这是工作示例:

def gen_comb(input_arr, result, index, curr_comb):
    if len(curr_comb) == len(input_arr):
        result.append(curr_comb)
        return

    for letter in input_arr[index]:
        gen_comb(input_arr, result, index + 1, curr_comb + letter)

    return result

print(gen_comb(input_arr=['abc', 'def'], result=[], index=0, curr_comb=""))

这是输出:['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']。稍微改变上面的代码就会出现问题:

def gen_comb(input_arr, result, index, curr_comb):
    if len(curr_comb) == len(input_arr):
        result.append(curr_comb)
        return

    for letter in input_arr[index]:
        curr_comb += letter
        gen_comb(input_arr, result, index + 1, curr_comb)

    return result

唯一的区别是在方法签名外添加了curr_comb += letter。在这种情况下，错误是 IndexError: list index out of range 但也有类似的错误结果示例。

问题是:

将表达式传递给递归函数与在传递给函数之前计算表达式有什么区别？

Answer 1

• 您的函数依赖于 len(curr_comb) == len(input_arr) 的基本情况。在满足基本情况的函数实例中，执行停止并且 for 语句不执行。您设计函数的方式是您希望在传递错误索引的同时满足基本情况。
• curr_comb += letter 更改函数当前 实例中curr_comb 的长度。这是在 for 循环中发生的。当next函数实例返回时，thisfor循环继续迭代，curr_comb的长度继续增加。
• 最终 len(curr_comb) > len(input_arr) 并且 next 函数实例中的基本情况失败，评估 for 语句并且代码尝试索引一个input_arr 中不存在的项目。

您可以通过打印或在 http://www.pythontutor.com/visualize.html#mode=edit 查看

---

这只是重申@JohnnyMopp 对您问题的评论的一种奇特方式。

---

我的回答特定于您的函数示例，并试图解释为什么第二个函数不起作用。

What is the difference between passing an expression to a recursive function and calculating the expression before to pass to the function?

对此的一般回答可能是:
两者都可以接受:但是

• 您必须设计基本案例以匹配其余功能。
• 您必须了解您的职能是如何运作的。
• 如果您更改了正在运行的递归函数中的某些内容，则很可能您将不得不更改其他内容。

---

然而，我越是思考它，我开始怀疑如果函数实例在中要在 < em>next 递归调用返回。似乎您应该只更改某些内容以便在下一个 实例中使用。我没有足够的经验，但它开始闻起来有腥味。也许有人会评论。我当然不记得读过任何反对它的禁令。