在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循环中发生的。当下一个函数实例返回时，这个for循环继续迭代，curr_comb的长度继续增加。你知道吗
• 最终len(curr_comb) > len(input_arr)和下一个函数实例中的基本情况失败，将计算for语句，代码尝试索引input_arr中不存在的项。你知道吗

您可以通过打印或在http://www.pythontutor.com/visualize.html#mode=edit上看到这一点

---

这只是一种花哨的方式来重申@johnnymapp对你问题的评论。你知道吗

---

我的答案是针对你的函数例子，并试图解释为什么第二个函数不起作用。你知道吗

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

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

• 您必须设计基本情况以匹配函数的其余部分。你知道吗
• 你必须了解你的职能是如何运作的。你知道吗
• 如果您在一个正在工作的递归函数中更改某些内容，则很可能您将不得不更改其他内容。你知道吗

---

然而，我越想越想，如果函数实例要在下一个递归调用返回后继续执行，那么改变它的状态是否是个坏主意。似乎您应该只为下一个实例更改某些内容。我没有足够的经验，但开始有点可疑了。也许有人会评论。我当然不记得读过任何反对它的禁令。你知道吗

Answer 2

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

上面的代码正在进行聚合。因此，如果input_arr[index]是'abcd'，而curr_comb是'h'，则展开循环的执行将如下所示：

gen_comb(input_arr, result, index+1, 'ha')
gen_comb(input_arr, result, index+1, 'hab')
gen_comb(input_arr, result, index+1, 'habc')
gen_comb(input_arr, result, index+1, 'habcd')

但实际上应该是：

gen_comb(input_arr, result, index+1, 'ha')
gen_comb(input_arr, result, index+1, 'hb')
gen_comb(input_arr, result, index+1, 'hc')
gen_comb(input_arr, result, index+1, 'hd')

它是原始代码的输出：

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