Recursion puzzle with key in the box

Question

I currently try to understand recursion on made up example. Imagine you have a briefcase, which can be opened by the key. The key is in the big box, which can contain other smaller boxes, which key might be in.

In my example boxes are lists. The recursion appears when we find the smaller box - we search it for the key. The problem is that my function can find the key if it is actually in the box and can't go back if there is nothing like 'key'.

Unfortunately, i could not understand how to go back if there is no key in the smaller box. Can you help me solve this puzzle? By the way, have a nice day! Here is the code (big box consists in the way when the key can be found and returned):

box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']

def look_for_key(box):
    for item in box:
        if isinstance(item, list) == True:
            look_for_key(item)
        elif item == 'key':
            print('found the key')
    key = item
    return key

print(look_for_key(box))

Answer 1

Iteration

The most closed to yours and yet readable solution I could find is:

def look_for_key(box):
    for item in box:
        if item == 'key':
            return item
        elif isinstance(item, list) and look_for_key(item) is not None:
            return look_for_key(item)
        else:
            pass

box = [['sock','papers'],['jewelry','key']]
look_for_key(box)
# ==> 'key'

I don't like it because its deduction condition includes a recursive call which is hard to interpret. It does not help to improve interpretability if you assign look_for_key(item) to a variable and check for not None afterwards. It is just similarly difficult to interpret. An equivalent but more interpretable solution is:

def look_for_key(box):
    def inner(item, remained):
        if item == [] and remained == []:
            return None
        elif isinstance(item, list) and item != []:
            return inner(item[0], [item[1:], remained])
        elif item == [] or item != 'key':
            return inner(remained[0], remained[1:])
        elif item == 'key':
            return item
    return inner(box[0], box[1:])

box = [['sock','papers'],['jewelry','key']]
look_for_key(box)
# ==> 'key'

It explicitly splits the tree to branches (see below what this means) with return inner(item[0], [item[1:], remained]) and return inner(remained[0], remained[1:]) instead of intrinsically reusing the recursive call conditionally during deduction - if look_for_key(item) is not None: return look_for_key(item) - with this line of code it is hard to see a diagram and understand in which direction the recursion goes.

The 2nd solution also makes it easier to infer the complexity using a tree diagram since you see the branches explicitly, for example remained[0] vs. remained[1:].

As inner is simply an iteration written in a functional way and for loop is a syntactic sugar to form iteration, both solutions should have similar complexity in principle.

Since you do not just want a solution but also a better understanding of recursion, I would try the following approach.

Mapping over Trees (Map-Reduce)

This is a typical text book tree recursion question. What you want is to traverse a hieratical data structure called tree. A typical solution is mapping a function over the tree:

from functools import reduce
def look_for_key(tree):
    def look_inner(sub_tree):
        if isinstance(sub_tree, list):
            return look_for_key(sub_tree)
        elif sub_tree == 'key':
            return [sub_tree]
        else:
            return []
    return reduce(lambda left_branch, right_branch: look_inner(left_branch) + look_inner(right_branch), tree, [])

box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']
look_for_key(box)
# ==> ['key']

To make it explicit I use tree, sub_tree, left_branch, right_branch as variable names instead of box, inner_box and so on as in your example. Notice how the function look_for_key is mapped over each left_branch and right_branch of the sub_trees in the tree. The result is then summarized using reduce (A classic map-reduce procedure).

To be more clear, you can omit the reduce part and keep only the map part:

def look_for_key(tree):
    def look_inner(sub_tree):
        if isinstance(sub_tree, list):
            return look_for_key(sub_tree)
        elif sub_tree == 'key':
            return sub_tree
        else:
            return None 
    return list(map(look_inner, tree))

look_for_key(box)
# ==> [None, None, [None, None, 'key'], None, None, None]

This does not generate your intended format of the result. But it helps to understand how the recursion works. map just adds an abstract layer to recursively look for keys into sub trees which is equivalent to the syntactic sugar of for loop provided by python. That is not important. The essential thing is decomposing the tree properly (deduction) and set-up proper base condition to return the result.

Native Tree Recursion

If it is still not clear enough, you can get rid of all abstractions and syntactic sugars and just build a native recursion from scratch:

def look_for_key(box):
    if box == []:
        return [] 
    elif not isinstance(box, list) and box == 'key':
        print('found the key')
        return [box]
    elif not isinstance(box, list) and box != 'key':
        return []
    else:
        return look_for_key(box[0]) + look_for_key(box[1:])

look_for_key(box)
# ==> found the key
# ==> ['key']

Here all three fundamental elements of recursion:

• base cases
• deduction
• recursive calls

are explicitly displayed. You can also see from this example clearly that there is no miracle of going out of an inner box (or sub-tree). To look into every possible corner inside the box (or tree), you just repeatedly split it to two parts in every smaller box (or sub tree). Then you properly combine your results at each level (so called fold or reduce or accumulate), here using +, then recursive calls will take care of it and help to return to the top level.

Both the native recursion and map-reduce approaches are able to find out multiple keys, because they traverse over the whole tree and accumulate all matches:

box = ['a','key','c', ['e', ['f','key']]]
look_for_key(box)
# ==> found the key
# ==> found the key
# ==> ['key', 'key']

Recursion Visualization

Finally, to fully understand what is going on with the tree recursion, you could plot the recursive depth and visualize how the calls are moving to deeper levels and then returned.

import functools 
import matplotlib.pyplot as plt

# ignore the error of unhashable data type
def ignore_unhashable(func): 
    uncached = func.__wrapped__
    attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')
    @functools.wraps(func, assigned=attributes) 
    def wrapper(*args, **kwargs): 
        try: 
            return func(*args, **kwargs) 
        except TypeError as error: 
            if 'unhashable type' in str(error): 
                return uncached(*args, **kwargs) 
            raise 
    wrapper.__uncached__ = uncached
    return wrapper

# rewrite the native recursion and cache the recursive calls
@ignore_unhashable
@functools.lru_cache(None)
def look_for_key(box):
    global depth, depths
    depth += 1
    depths.append(depth)
    result = ([] if box == [] else
              [box] if not isinstance(box, list) and box == 'key' else
              [] if not isinstance(box, list) and box != 'key' else
              look_for_key(box[0]) + look_for_key(box[1:]))
    depth -= 1
    return result
    
# function to plot recursion depth
def plot_depths(f, *args, show=slice(None), **kwargs):
    """Plot the call depths for a cached recursive function"""
    global depth, depths
    depth, depths = 0, []
    f.cache_clear()
    f(*args, **kwargs)
    plt.figure(figsize=(12, 6))
    plt.xlabel('Recursive Call Number'); plt.ylabel('Recursion Depth')
    X, Y = range(1, len(depths) + 1), depths
    plt.plot(X[show], Y[show], '.-')
    plt.grid(True); plt.gca().invert_yaxis()

box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs']
plot_depths(look_for_key, box)

Whenever the function got called recursively, the curve goes to a deeper level - the downward slash. When the tree/sub-tree is splitted to left and right branches, two calls happen at the same level - the horizontal line that connected two dots (two calls look_for_key(box[0]) + look_for_key(box[1:])). When it traverses over a complete sub-tree (or branch) and reaches to the last leave in that sub-tree (a base condition when a value or [] is returned), it starts to go back to upper levels - the valley in the curve. If you have multiple sub/nest lists there will be multiple valleys. Eventually it traverses over the whole tree and returns the results

You can play with boxes (or trees) of different nest structures to understand better how it works. Hopefully these provide you enough information and a more comprehensive understanding of tree-recursion.

Answer 2

Integrating the above comments:

box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']

def look_for_key(box):
    for item in box:
        if isinstance(item, list) == True:
            in_box = look_for_key(item)
            if in_box is not None:
                return in_box
        elif item == 'key':
            print('found the key')
            return item
    # not found
    return None

print(look_for_key(box))

which prints:

found the key
key

If the key is deleted from the box, executing the code prints:

None