递归运算顺序疑问：maxVal函数withVal无无限循环及赋值逻辑

先把你提到的递归代码贴出来方便分析：

def maxVal(toConsider, avail):
    if toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getCost() > avail:
        result = maxVal(toConsider[1:], avail)
    else:
        nextItem = toConsider[0]
        withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
        withVal += nextItem.getValue()
        withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    return result

一、为什么withVal不会陷入无限循环？ #

其实递归不会无限跑起来的核心，是它有明确的终止条件，而且每次调用都会让问题规模变小。咱们一步步拆来看：

1. 每次调用maxVal时，传入的第一个参数是toConsider[1:]——也就是把当前列表的第一个元素砍掉，剩下的部分传进去。比如一开始toConsider是[A,B,C,D]，第一次递归调用就变成[B,C,D]，下一次是[C,D]，再下一次[D]，最后变成空列表[]。
2. 当toConsider == []或者avail == 0的时候，函数直接返回(0, ())，这就是递归的“终止锚点”。到了这一步，递归就不再继续深入，开始往回走了。

举个简单的流程例子：

• 调用maxVal([A,B], 10) → 进入else分支，调用maxVal([B], 10 - A.cost)
• 调用maxVal([B], ...) → 再进入else分支，调用maxVal([], ... - B.cost)
• 调用maxVal([], ...) → 触发终止条件，返回(0, ())
• 回到maxVal([B], ...)这一层，计算withVal = 0 + B.value，再调用maxVal([], ...)拿withoutVal，然后比较返回结果
• 再回到maxVal([A,B],10)这一层，拿到withVal和withoutVal，比较后返回最终结果

所以每一次递归都是在“拆小问题”，直到触碰到终止条件，根本不会无限循环下去。

二、先递归调用再累加value的赋值顺序为什么能正常执行？ #

这个其实是递归“先深度遍历到底，再回溯计算”的特性决定的，咱们拆解else分支的执行顺序：

nextItem = toConsider[0]
# 第一步：先递归解决「不包含当前item，剩余容量减去当前item成本」的子问题
withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
# 第二步：把当前item的价值加到子问题的结果上
withVal += nextItem.getValue()

这里的关键是：只有当子问题完全解决，拿到了withVal和withToTake的确定结果之后，才会执行累加当前item价值的操作。

还是拿[A,B]的例子来说：

1. 处理A的时候，先去解决[B]在10 - A.cost容量下的最大价值——这会一直递归到空列表，拿到子问题的结果(B.value, (B,))
2. 回到A这一层，把A的value加到这个子问题的value上，得到A.value + B.value，同时把A加入到选中的物品元组里
3. 接下来再去解决「不选A，容量10」的子问题，也就是maxVal([B],10)，拿到它的结果
4. 最后比较选A和不选A的价值，返回更大的那个

整个过程是“先把当前item后面的所有子问题都算清楚，再回头把当前item的价值加进去”，完全不会混乱——因为子问题的结果已经是确定的了，累加只是做个简单的数值运算而已。

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