python 中的函数输入和递归

Question

这是一个愚蠢的问题。这里是：

我有两个列表，候选人输入和约束输入。下面的函数通过消除不能成为获胜者的候选者，直到只剩下一个，来找到针对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

它在不复制的情况下“工作”的原因是，当您进行递归调用时，您不会从中返回任何内容。每个递归调用都会重新过滤原始数据，一旦您从所有内容返回，原始数据就已被完全重新过滤。如果创建副本，则会连续创建经过更多过滤的副本，但原始数据不会更改，并且无法从调用范围访问经过更多过滤的副本。

这是通过返回递归调用的结果来修复的。在进行初始调用时，您将捕获返回值（并且可能将其重新分配给原始变量）。当然，为了让事情正常工作，您需要在返回的任何地方都返回相同类型的东西。因此，您将返回一个 (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]

当然，现在函数体已经清理完毕，您应该能够简单地了解如何转换为迭代。另外，这里还有一个不必要的复杂化：由于我们要确定每个候选者的违规次数，因此确定所有违规者并将其过滤掉是没有意义的：我们可以直接通过相反的条件（左）确定所有好的候选者作为练习）。

Answer 2

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