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]

当然，现在函数的主体已经整理好了，你应该能轻松看到如何转换为迭代方式。此外，这里还有一个不必要的复杂性：因为我们要为每个候选者确定违规数量，所以确定所有违规者并将其过滤掉是没有意义的：我们可以直接通过相反的条件来确定所有合格的候选者（留作练习）。