最近，我在try 编写一个函数，在任意深度嵌套的序列中的任意位置找到一个原始值，并返回到达该值的路径(作 for each 连续嵌套序列中的索引列表，按顺序).我遇到了一个意想不到的障碍:函数正在查找结果，但没有返回结果！函数不返回正确的输出，而是不断返回仅在试图在序列中查找项目not时才应产生的输出.
通过在函数中的不同位置放置print条语句，我发现问题在于，在实际找到该项的递归调用之后，其他没有找到该项的语句也在返回，而且显然比找到该项的语句返回的时间晚.这意味着最终结果是从"成功"值重置为"失败"值，除非"成功"值是最后遇到的.
我试图通过在函数中添加一个额外的条件来解决这个问题，以便在成功 case 中尽早返回，试图抢占导致最终结果不正确的额外的、不必要的递归调用.现在，this是我遇到问题的根本原因:
没有办法知道which个递归调用(如果有的话)会提前找到该项，一旦其中一个找到了，它就无法与其他调用"通信"！
我能想出的避免这个更深层次问题的唯一方法是完全重构函数，在遇到"成功"条件的情况下，使用"成功"输出在函数外部"设置"一个变量.外部全局变量开始时设置为"未能在序列中找到项"值，除非在"成功"情况下，否则不会重置.所有其他递归调用都是return次，什么都不做.这看起来很难看，效率也很低，但它确实有效.
第一次try
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (First Attempt)
# Works on 'result1' but not on 'result2'
# Searches for 'item' in sequence (list or tuple) S, and returns a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns a tuple containing an empty list and -1
def traverse(S, item, indices=[], atDepth=0):
# If the sequence is empty, return the 'item not found' result
if not S:
return ([], -1)
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
return (indices + [i], atDepth)
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
return traverse(S[i], item, indices + [i], atDepth + 1)
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " + str(item) + " in " + str(S) + ".")
return ([], -1)
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
result1 = traverse(L, 7)
result2 = traverse(L, 9)
print("-------------------------------------------")
print(result1)
print("-------------------------------------------")
print(result2)
第二次try
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (Second Attempt)
# Does not work on either test case
# Searches for 'item' in sequence (list or tuple) S, and returns a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns a tuple containing an empty list and -1
def traverse(S, item, indices=[], atDepth=0, returnValue=None):
# If the sequence is empty, return the 'item not found' result
if not S:
print("Sequence S is empty.")
return ([], -1)
# --- ATTEMPTED FIX:
# If the item is found before the end of S is reached,
# do not perform additional searches. In addition to being
# inefficient, doing extra steps would cause incorrect false
# negatives for the item being in S.
# --- DOES NOT WORK: the underlying issue is that the multiple recursive
# calls generated at the same time can't communicate with each other,
# so the others don't 'know' if one of them already found the item.
elif returnValue:
print("Inside 'elif' statement!")
return returnValue
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
# Return the depth and index at that depth of the item
print("--- Found item " + str(item) + " at index path " + str(indices) + " in current sequence")
returnValue2 = (indices + [i], atDepth)
print("--- Item " + str(item) + " is at index path " + str(returnValue2) + " in S, SHOULD RETURN")
#return returnValue2 # THIS DIDN'T FIX THE PROBLEM
#break # NEITHER DID THIS
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
# CANNOT USE 'return' BEFORE RECURSIVE CALL, as it would cause any items
# in the outer sequence which come after the first occurrence of a nested
# sequence to be missed (i.e. the item could exist in S, but if it is
# after the first nested sequence, it won't be found)
traverse(S[i], item, indices + [i], atDepth + 1, returnValue) # CAN'T USE 'returnValue2' HERE (out of scope);
# so parameter can't be updated in 'if' condition
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " + str(item) + " in " + str(S) + ".")
return ([], -1)
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
result1 = traverse(L, 7)
result2 = traverse(L, 9)
print("-------------------------------------------")
print(result1)
print("-------------------------------------------")
print(result2)
第三次也是最后一次try ——成功了，但并不理想！
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (Third Attempt)
# This 'kludge' is ** HIDEOUSLY UGLY **, but it works!
# Searches for 'item' in sequence (list or tuple) S, and generates a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns nothing (implicitly None)
# The results of calling the function are obtained via external global variables.
# This 3rd version of 'traverse' is thus actually a void function,
# and relies on altering the global state instead of producing an output.
# ----- WORKAROUND: If the result is found, have the recursive call that found it
# send it to global scope and use this global variable as the final result of calling
# the 'traverse' function.
# Initialize the global variables to the "didn't find the item" result,
# so the result will still be correct if the item actually isn't in the sequence.
globalVars = {'result1': ([], -1), 'result2': ([], -1)}
def traverse(S, item, send_output_to_var, indices=[], atDepth=0):
# If the sequence is empty, return *without* doing anything to the global variable.
# It is already initialized to the "didn't find item" result.
if not S:
return
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
# Set the global variable to the index path of 'item' in 'S'.
globalVars[send_output_to_var] = (indices + [i], atDepth)
# No need to keep on doing unnecessary work!
return
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
# Don't use 'return' before the recursive call, or it will miss items
# in the outer sequence after a nested sequence is encountered.
traverse(S[i], item, send_output_to_var, indices + [i], atDepth + 1)
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item.
else:
# Return *without* setting the global variable, as it is
# already initialized to the "didn't find item" result.
return
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
traverse(L, 7, 'result1')
traverse(L, 9, 'result2')
print("-------------------------------------------")
print(globalVars['result1'])
print("-------------------------------------------")
print(globalVars['result2'])
我想知道我是否遗漏了什么，事实上，有一种方法可以在不使用外部变量的情况下实现这一点.最好的解决方案是，当其中一个递归调用返回成功结果时，以某种方式"关闭"所有其他递归调用，但我认为这是不可能的(我希望这一点是错误的！).或者可能是某种"优先级队列"，将return个"成功" case 递归调用(如果存在)延迟到after个"失败" case 递归调用全部返回？
我看了这个类似的问题:Recursively locate nested dictionary containing a target key and value