python中的函数输入和递归

Question

这是一个毫无疑问的问题。这里有：

我有两个名单，candidates_input和constraint_input。下面的函数通过在constraint_input中给出约束的给定排序，在candidates_input中查找获胜候选者，方法是排除不能成为赢家的候选者，直到剩下一个。因此，我从两个输入列表中删除项目 - 失去了已经告诉他们所有可能的候选项和约束条件，然后转向下一个约束条件。

虽然我不想实际修改原始输入列表，因为我会再次需要它们。但在函数的开头插入这样的事情：

remaining_candidates = candidates_input[:] 
remaining_constraints = constraint_input[:] 

然后替代函数内旧的这些新名字似乎打破递归。我究竟做错了什么？

def OT_eval(candidates_input, constraint_input): #chooses an optimal candidate given candidates and constraint ranking 
    constraint = constraint_input[0]    #highest ranked constraint 
    violations_list = [(len(re.findall(constraint, candidate)), candidate) for candidate in candidates_input] 
    violations_list.sort() 
    """ 
    Creating list of (num violations, candidate) duples for each candidate, then sorting on num violations 
    """ 
    for pair in violations_list:     #checking each candidate against known optimal candidate 
     if pair[0] > violations_list[0][0]:  #num violations > minimal violations 
      candidates_input.remove(pair[1])  #removing suboptimal candidate 
    if len(candidates_input) > 1 and len(constraint_input) > 0: #if further constraints needed, 
     constraint_input.remove(constraint)      #remove current constraint and recurse 
     OT_eval(candidates_input, constraint_input) 
    elif len(candidates_input) == 1: 
     optimal_candidate = candidates_input[0] 
     print "Optimal Candidate: ", optimal_candidate 
     return optimal_candidate 
    elif len(candidates_input) > 1 and len(constraint_input) == 0: #more than one candidate left, but no more constraints 
     raise ValueError("Optimal candidate cannot be determined: check constraints") 

Answer 1

在我看来，你应该循环你的constraint_input而不是递归？

Answer 2

它“工作”而不复制副本的原因是，当你进行递归调用时，你不会从中返回任何东西。每次递归调用都会重新过滤原始数据，一旦您从所有内容中返回，原始数据都会被完全重新过滤。如果您制作副本，则会创建相继更多筛选的副本，但原始数据保持不变，并且无法从调用作用域访问更多筛选的副本。

这是通过递归调用的结果由return修复的。在进行初始调用时，您将捕获返回值（也可能将其重新分配给原始变量）。当然，为了正常工作，你需要在任何地方返回相同类型的东西。因此，您将返回一个（candidates_input，constraint_input）元组，以便获得该数据，并且让呼叫站点解释结果。你的代码很混乱;责任没有妥善分开。这里有两个任务：过滤数据，并确定过滤数据的含义。

当您编写递归代码时，通常希望它处于功能样式中。这意味着：不要修改现有的东西，而是创建修改后的版本。为了保持一致性和整洁，即使是为了分步骤，你也应该这样做。

def OT_eval(candidates_input, constraint_input): 
    # It's much cleaner to handle base cases for recursion **first**. 
    if not (constraint_input and candidates_input): 
     # We ran out of one or the other. BTW, your original code doesn't 
     # consider the case of an overly constrained situation. 
     return (candidates_input, constraint_input) 

    constraint = constraint_input[0] 
    # At first I was going to replace the call to `.sort()` by using 
    # the free function `sorted` to maintain the "functional" theme. 
    # However, you don't really need to sort the list, as far as I can 
    # tell; you just need to find the minimum and use it as a basis for 
    # comparison. 
    violations = [ 
     (len(re.findall(constraint, candidate)), candidate) 
     for candidate in candidates_input 
    ] 

    # Now we create "all candidates with more than the minimum violations" 
    minimal_violations = min(violations)[0] 
    violators = [ 
     candidate 
     for violation_count, candidate in violations 
     if violation_count > minimal_violations 
    ] 
    # And hence "all candidates without that many violations" 
    good_candidates = [ 
     candidate 
     for candidate in input_candidates 
     if candidate not in violators 
    ]  

    # And now we can recurse. 
    return OT_eval(good_candidates, constraint_input[1:]) 

# Then, outside, we do the actual result processing and output: 

final_candidates, final_constraints = OT_eval(candidates, constraints) 

if final_constraints: 
    print "No candidates survived the selection process." 
elif len(final_candidates) != 1: 
    print "Couldn't determine a winner." 
else: 
    print "The winner is:", final_candidates[0] 

当然，现在的函数体被清理，你应该能够看到平凡如何转换到迭代。此外，这里还有一个不必要的复杂因素：由于我们正在确定每个候选人的违规次数，因此确定所有违规者并将其过滤掉是没有意义的：我们可以直接通过相反的条件确定所有合适的候选人（左作为练习）。