One of many recursive calls of a function found the correct result, but it can't "tell" the others. Is there a better fix than this ugly workaround?

user_18248018 0
Viewed 132

Recently, I was experimenting with writing a function to find a primitive value anywhere within an arbitrarily deeply nested sequence, and return the path taken to get there (as a list of indices inside each successive nested sequence, in order). I encountered a very unexpected obstacle: the function was finding the result, but not returning it! Instead of the correct output, the function kept returning the output which should only have been produced when attempting to find an item not in the sequence.

By placing print statements at various points in the function, I found that the problem was that after the recursive call which actually found the item returned, others which did not find the item were also returning, and evidently later in time than the one that found it. This meant that the final result was getting reset to the 'fail' value from the 'success' value unless the 'success' value was the last thing to be encountered.

I tried fixing this by putting an extra conditional inside the function to return early in the success case, trying to preempt the additional, unnecessary recursive calls which were causing the incorrect final result. Now, this is where I ran into the root cause of the problem:

There is no way of knowing which recursive call (if any) will find the item beforehand, and once one of them does find it, it has no way of 'communicating' with the others!

The only way I could come up with of avoiding this deeper issue was to completely refactor the function to 'set' a variable outside itself with the 'success' output if and only if the 'success' condition is encountered. The external, global variable starts out set to the 'failed to find item in sequence' value, and is not reset except in the 'success' case. All the other recursive calls just return without doing anything. This seems very ugly and inefficient, but it does work.

FIRST ATTEMPT

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

SECOND ATTEMPT

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

THIRD AND FINAL ATTEMPT -- Working, but not ideal!

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

I was wondering if I'm missing something and there is in fact a way of making this work without the use of external variables. The best possible solution would be somehow 'shutting down' all the other recursive calls as soon as one of them returns the success result, but I don't believe this is possible (I'd love to be wrong about this!). Or maybe some kind of 'priority queue' which delays the return of the 'success' case recursive call (if it exists) until after all the 'fail' case recursive calls have returned?

I looked at this similar question: Recursively locate nested dictionary containing a target key and value but although the accepted answer here https://stackoverflow.com/a/59538362/18248018 by ggorlen solved OP's problem and even mentions what seems to be this exact issue ("matched result isn't being passed up the call stack correctly"), it is tailored towards performing a specific task, and doesn't offer the insight I'm looking for into the more general case.

recursion algorithm python
4 Answers

Your first attempt is almost perfect, the only mistake is that you return the result of searching through the first list/tuple at the current depth, regardless of whether the item was found or not. Instead, you need to check for a positive result, and only return if it is one. That way you keep iterating through the current depth until you either find the item or it is not found at all.

So you need to change:

return traverse(S[i], item, indices + [i], atDepth + 1)

to something like:

t = traverse(S[i], item, indices + [i], atDepth + 1) 
if t != ([], -1):
    return t

Full code:

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):
                t = traverse(S[i], item, indices + [i], atDepth + 1) 
                if t != ([], -1):
                    return t
            
        # 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)

Output for your two test cases:

>>> traverse(L, 7)
([3, 1, 2, 4], 3)
>>> traverse(L, 9)
We looked everywhere but didn't find 9 in [6, 6.25, 6.5, 6.75, 7].
We looked everywhere but didn't find 9 in (4, 5, [6, 6.25, 6.5, 6.75, 7]).
We looked everywhere but didn't find 9 in [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])].
We looked everywhere but didn't find 9 in [8, ()].
We looked everywhere but didn't find 9 in [[8, ()]].
([5, 0, 0, 0], 3)

Note as pointed out by @FreddyMcloughlan, atDepth is simply the length of the returned list minus 1. So you can remove that parameter from the function call and just use:


def traverse(S, item, indices=[]):
    # 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], len(indices))
            
            # Recursive step (depth-first):  enter nested sequence
            # and repeat procedure from beginning
            elif type(S[i]) in (list, tuple):
                t = traverse(S[i], item, indices + [i]) 
                if t != ([], -1):
                    return t
            
        # 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)
user_94737640

I'd write it differently, using the result of the recursive calls to decide whether to return immediately or continue searching. My version returns a non-empty list of indices if the item was found, or None otherwise.

def traverse(S, item):
    for i, element in enumerate(S):
        if element == item:
            return [i]
        if type(element) in (list, tuple):
            if indices := traverse(element, item):
                indices.insert(0, i)
                return indices

Results for your two tests (Try it online!):

[3, 1, 2, 4]
[5, 0, 0, 0]

I don't pass in a list, instead build the list backwards only from the location of the item (or if it's nowhere, then I don't build any list at all). This is much less work, although inserting at 0 makes it quadratic, although much faster than copying slices. If you want it linear, you could wrap this recursive function in another function and have the recursive function append the indices and have the wrapper function reverse the list before returning it to the original outside caller. The wrapper function would also let you turn the "non-empty list or None" result into something else (like a pair with depth), if you want.

user_126710570

Since refactoring the traverse function to be iterative instead of recursive was discussed in the comments, here is that version too for completeness' sake:

# Iterative-only version of the same function from the question

def traverse(S, item):
    indices = []
    sequence = S
    depth = 0

    # By definition, if the sequence is empty, you won't find any items in it.
    # Return the 'item not found' result.
    if not S:
        return ([], -1)

    else:
        # You have to start somewhere :D
        indices.append(0)

        while depth > -1:
            # Go back up one level once the end of a nested sequence is reached.
            while indices[depth] == len(sequence):
                depth -= 1
                
                # If the depth ever gets below 0, that means that we've scanned
                # the entire length of the outermost sequence and not found the
                # item.  Return the 'failed to find item' result.
                if depth == -1:
                    return ([], -1)

                # Remove the entry corresponding to index in the innermost
                # nested sequence we just exited
                indices.pop()

                # Reset 'sequence' using the outermost sequence S and the indices
                # computed so far, to get back to the sequence which contained
                # the previous one
                sequence = S
                for i in range(len(indices) - 1):
                    sequence = sequence[indices[i]]

                indices[depth] += 1
                # And return to the top of the outer 'while' loop to re-check
                # whether to go down another level
                continue
                
            # Success:  found the item at depth 'depth', in sequence 'sequence',
            # at index 'indices[depth]` inside that sequence.  Return 'indices'
            # and 'depth'.
            if sequence[indices[depth]] == item:
                return (indices, depth)
            
            # Recursion replacement:  enter the nested subsequence and increase the depth
            # as long as the nested subsequence is not empty.  If it is empty, treat it
            # as if it were a non-sequence type.
            elif (type(sequence[indices[depth]]) in (list, tuple)) and (sequence[indices[depth]]):
                sequence = sequence[indices[depth]]
                depth += 1
                indices.append(0)
                        
            # The item being compared is not a sequence type and isn't equal to 'item', so increment
            # the index without increasing the depth
            else:
                indices[depth] += 1
                
        # If all of S has been searched and item was not found,
        # return the 'failed to find item' result
        return ([], -1)
                            

L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]

# Demonstrating the function's use:  search for numbers from 0 to 10 in list L,
# in increments of 0.5
for i in range(21):
    outputString = "Looking for " + (str(i/2) if (i/2 % 1) else str(int(i/2))) + " in L: "
    indices, depth = traverse(L, i/2)
    if indices:
         print(outputString + "found at depth " + str(depth) + " by index path " + str(indices))
    else:
        print(outputString + "Not found.")

I've heard that iterative algorithms can be faster than recursive ones, so I tried benchmarking all 3 working versions using time.time(). For all 3, I used the same 'busy work' test shown below:

L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]

startTime = time.time()

for i in range(1000):
    for j in range(21):
        traverse(L, j/2)

finishedAt = time.time()
print("[WHICH VERSION] took " + str(finishedAt - startTime) + " seconds")

and got these results:

For the original recursive function with Nick's fix applied: Original recursive version took 0.14863014221191406 seconds

For Kelly's recursive version: Quadratic recursive version took 0.11344289779663086 seconds

For the iterative version: Iterative version took 0.1890261173248291 seconds

As I expected, Kelly's version, which has optimizations that my original function didn't, is faster than the original. I haven't implemented the linear version with the outer wrapping function that reverses the list yet, but I expect that that will be even faster.

Unfortunately, the iterative version seems to actually be slower than the original version of the recursive function with no optimizations, so I guess I'll take it over to the code review site to see where it could be improved...

References: Original with bug fix: See Nick's answer here: https://stackoverflow.com/a/72180834/18248018

Kelly's recursive version: https://stackoverflow.com/a/72189848/18248018

Iterative version: see above

user_182480180

You need to stack the indexes as you go, and assign the recursive function a success flag. When you perform a recursive call, you push the new index. When the function returns, in case of failure you pop and continue the search, and in case of success you do nothing but return success. In the end, the stack will be either empty or filled with the solution.

The stack can be a global variable or be passed as an argument.

user_11965490
Related