递归在此代码中究竟是如何工作的

Question

我有这个代码，它不是我的，我在网上看到了它，我想知道递归是如何工作的，有人可以解释一下！

(这个函数接受整数(距离(列表和一个值'r'让我们说10(它返回我们如何使用距离达到100的所有可能性(假设列表是[3,5,2,5]，值r是10！所以要制作10我们需要[5,5]或[3,2,5]，这是代码：

def greedy(r, distances):
if r < 0:
return []
if r == 0:
return [[]]
solutions = []
for last_distance in d:
combos = greedy(r - last_distance, d)
for combo in combos:
combo.append(last_distance)
if(not solutions.__contains__(combo)):
solutions.append(combo)
return solutions

我希望我把自己说清楚

了

Answer 1

我建议使用python打印函数

print("")

在多个位置实际看到递归发生。你会得到一个比试图向你解释更好的主意。

虽然功能本身很简单。对于距离中的每个元素，该函数从所需的r值中减去该元素，并使用 if 条件检查该值。 如果r值为零，即对于距离中的某些元素，它们的总和为r，返回一个多重列表，其中还具有所述元素。

最后，其总和与r相加的元素的完整列表将追加到solution列表中并返回。

Answer 2

假设给定一个长度为n的列表distances0，您可以返回列表中i1,..,in的所有元组，该元组的总和为任何数字r的数字r。

您希望对长度n+1的列表distances执行相同的操作。 由于您知道如何解决大小n列表的问题，您将执行以下操作：对于distances的每个元素last_distance，从类似于distances但没有元素last_distance(因此长度为n(的列表distances0返回所有总和为r-last_distance的元组i1,...,in。

我认为代码中可能存在一些错误，这里应该是一个工作版本：

def greedy(r, distances):
if r < 0:
return []
if r == 0:
return [[]]
solutions = []
for i in range(len(distances)):
d = distances[:i]+distances[i+1:]
last_distance = distances[i]
combos = greedy(r - last_distance, d)
for combo in combos:
combo.append(last_distance)
if(not solutions.__contains__(combo)):
solutions.append(combo)
return solutions