代码之家 › 专栏 › 技术社区 › Bartholomas

无法理解递归函数Python

recursion function python

Bartholomas · 技术社区 · 8 年前

我已经看了几个小时这个问题的解决方案(下面),但我不知道递归是如何工作的。有人能用基本术语解释一下它是如何工作的吗。

既然组是追加然后弹出的,弹出的列表不是总是等于零吗[]?

# Given a  list of ints, is it possible to choose a group of some of the   
# ints, such that the group sums to the given target?
#   0, 2, 4, 8, 10 -> True                                                  
#   0, 2, 4, 8, 14 -> True                                                  
#   0, 2, 4, 8, 9 -> False   

def sum_checker(ints, total, group, index):
    if sum(group) > total:            # backtracking
        return False
    if index == len(ints):            # BASE CASE
        return sum(group) == total

    group.append(ints[index])
    if sum_checker(ints, total, group, index + 1):
        return True
    group.pop()
    return sum_checker(ints, total, group, index + 1)


ints = [int(input()) for i in range(int(input()))]
total = int(input())
group = []
print(sum_checker(ints, total, group, 0))

3 回复 | 直到 8 年前

OneCricketeer Gabriele Mariotti 8 年前

弹出列表不总是等于零吗[]?

不总是这样。在第三个if语句中,它递归地添加到组列表中,并且只有当调用堆栈返回时(当组的总和超过总数,或者索引超出输入范围时),才会弹出最近推送的值。

按照第一个输入的执行顺序,下面是组值

0   
0, 2   
0, 2, 4  
0, 2, 4, 8... Sum is greater than 10, return False   
8 is popped, and the previous index increases      
0, 2, 4.... The index is out of range, and the group sum is not the total
4 is popped and the previous index increases   
0, 2, 8... This is equal to 10, so we return True back up the call stack

在展开递归结束时,是的,组列表将为空,但输出只需要一个布尔值,而不需要跟踪与条件匹配的组

lincr 8 年前

好啊让我们先来思考这个没有真正代码的问题。想想这个策略:

我们测试 ints 一个接一个地,通过选取当前值加上之前的选择进行检查,我们可以得到目标和。
例如 ints= [1, 2, 4, 8] ,则, target = 11 。
我们尝试选择 1 ,我们不知道在检查其他元素之前是否可以得到目标,所以我们继续检查,保持 1. 在你的手中。
现在我们见面了 2 ,仍然不知道,只需选择并继续。
与相同 4 。
哎呀,我们有 sum=1+2+4+8 = 13 > 11 。[1,2,4,8]是一个糟糕的选择计划。让我们从结尾往下看,如果我们有其他选择,那就检查一下。滴 8 。
现在我们有了 sum=1+2+4=7 ,但我们无法添加更多元素,因为我们已达到 ints公司 。滴 4. 看看是否有更多的选择。
我们现在等待 1+2 并且应该从 8. ,这是 11 哦!我们成功了!

所以你可以自己用铅笔和纸试试这个过程。这里的核心思想是保持 我们选择的内容 数组,即 group 然后检查 如果我们能够基于此选择+新元素达到目标 。如果没有,请修改 我们选择的内容 阵列并继续。

SCB 8 年前

关于您对 group 正在追加和弹出。记住这句话

if sum_checker(ints, total, group, index + 1):

再次开始搜索(这次使用下一个索引)。用你的例子说。

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[],
    index=0
)

我们第一次打组时,我们附加 0 到 组 ,所以我们打电话 sum_checker 带参数。

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[0],
    index=1
)

然后,自 组 已经有一个元素,我们附加 2 到 组 。因此,我们有:

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[0, 2],
    index=2
)

也就是说,我们开始加油 组 在我们到达之前 .pop() 。如果 sum() 属于 组 变得太大,然后我们先 。pop() ,然后在没有添加最后一个元素的情况下再次开始检查。