Python中的递归

Question

这个问题是关于写一个递归函数，叫做“def EhMensuravel (target, weight)”，它的作用是判断能否用一组给定的砝码在天平上称出一个想要的目标值。可用的砝码存储在一个叫“weights”的列表里。

需要记住的是，这些砝码可以放在与目标砝码相对的盘子上，也可以放在目标砝码的同一盘子上，或者根本不使用。

我写的代码是这样的，但似乎哪里出了问题。

weights = [1, 2, 3]
matrix = []

def createaMatrix():
    for i in range(len(weights)):
        matrix.append([])
    for j in range(3):
        for i in range(len(weights)):
            if j==0:
                matrix[j].append(weights[i])
            if j==1:
                matrix[j].append(-weights[i])
            if j==2:
                matrix[j].append(0)

createMatrix()


def EhMensuravel(entry, weights, final_weight=0):
    if final_weight == entry:
        return True
    for j in range(3):
        for i in range(len(weight)):
            final_weight += matrix[i][j]
            return EhMensuravel(entry, weight[1:], final_weight)

编辑：举个例子，当我尝试 print EhMensuravel(4, weights) 时，输出是：

>>> 
1
2
3
None
>>> 

Answer 1

你可以让递归变得很简单，即使不使用全局矩阵也可以，像这样：

weights = [1, 2, 3]

def EhMensuravel(entry, weights, weight_idx = 0):
    if entry == 0:
        return True

    if weight_idx == len(weights):
        return False

    if EhMensuravel(entry + weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry - weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry, weights, weight_idx+1):
        return True

    return False

print EhMensuravel(4, weights)

第一个if语句的意思是0是可以测量的。第二个if语句则确保还有剩余的重量。接下来的三个递归调用会通过加上、减去或忽略当前的重量来更新当前的重量entry，然后从下一个重量开始重新搜索。如果没有找到解决方案，就会返回False。