Один из многих рекурсивных вызовов функции нашел правильный результат, но не может «сказать» другим. Есть ли лучшее решение, чем этот уродливый обходной путь?

Недавно я экспериментировал с написанием функции для поиска примитивного значения в любом месте произвольно глубоко вложенной последовательности и возврата пути, по которому туда добраться (в виде списка индексов внутри каждой последовательной вложенной последовательности, по порядку). Я столкнулся с очень неожиданным препятствием: функция находила результат, но не возвращала его! Вместо правильного вывода функция продолжала возвращать вывод, который должен был быть получен только при попытке найти элемент нет в последовательности.

Размещая операторы print в различных точках функции, я обнаружил, что проблема заключалась в том, что после рекурсивного вызова, который фактически нашел возвращенный элемент, другие, которые не нашли элемент, также возвращались, и, очевидно, позже по времени, чем тот, который нашел Это. Это означало, что окончательный результат сбрасывался на значение «неудача» из значения «успех», если только значение «успех» не было последним, с чем приходилось сталкиваться.

Я попытался исправить это, поместив в функцию дополнительное условие для раннего возврата в случае успеха, пытаясь упредить дополнительные, ненужные рекурсивные вызовы, которые вызывали неверный конечный результат. Теперь в это я столкнулся с основной причиной проблемы:

Нет никакого способа узнать, что рекурсивный вызов который (если есть) найдет элемент заранее, и как только один из них найдет его, он не сможет «общаться» с другими!

Единственный способ, который я мог придумать, чтобы избежать этой более глубокой проблемы, состоял в том, чтобы полностью реорганизовать функцию, чтобы «установить» переменную вне себя с выходом «успех», если и только если встречается условие «успеха». Внешняя глобальная переменная изначально устанавливается в значение «не удалось найти элемент в последовательности» и не сбрасывается, кроме как в случае «успеха». Все остальные рекурсивные вызовы просто return ничего не делают. Это кажется очень уродливым и неэффективным, но это работает делает.

ПЕРВАЯ ПОПЫТКА

# 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)

ВТОРАЯ ПОПЫТКА

# 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)

ТРЕТЬЯ И ПОСЛЕДНЯЯ ПОПЫТКА -- Работает, но не идеально!

# 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 рекурсивного вызова «успешного» случая (если он существует) до тех пор, пока после не вернутся все рекурсивные вызовы «неудачного» случая?

Я посмотрел на этот похожий вопрос: Рекурсивно найти вложенный словарь, содержащий целевой ключ и значение но хотя принятый здесь ответ https://stackoverflow.com/a/59538362/18248018 от ggorlen решил проблему OP и даже упоминает то, что кажется именно этой проблемой («сопоставленный результат неправильно передается вверх по стеку вызовов»), он предназначен для выполнения конкретной задачи и не Я не предлагаю понимания, которое я ищу в более общем случае.