The reason it "works" without making a copy is that when you make the recursive call, you don't return anything from it. Each recursive call re-filters the original data, and once you've returned from everything, the original data has been completely re-filtered. If you make copies, then successively more-filtered copies are created, but the original data is unchanged, and there is no way to access the more-filtered copies from the calling scope.
This is fixed by returning the result of the recursive call. At the point where you make the initial call, you would capture the return value (and perhaps reassign it to the original variable). Of course, for things to work properly, you'd need to return the same kind of thing everywhere that you return. So you'd return a (candidates_input, constraint_input) tuple so that you have that data, and let the call site interpret the result. Your code is confused; responsibility is not properly separated. There are two tasks here: filtering the data, and determining what the filtered data means.
When you write recursive code, you want it to be in a functional style, generally. That means: don't modify things in place, but instead create the modified versions. For consistency and neatness, you should be doing this even for sub-steps.
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]
Of course, now that the body of the function is cleaned up, you should be able to see trivially how to convert to iteration. Also, there's a needless complication here: since we're determining the number of violations for every candidate, it makes no sense to determine all the violators and filter them out: we could just determine all the good candidates directly via the opposite condition (left as an exercise).
