Issue 9: Using Iteration on a Recursive Problem

I didn't fail the test, I just found 100 ways to do it wrong.
- Benjamin Franklin  

During our Lab #8, we had a rather unique challenge: create the recursive count_less(item) method without using recursion. This came as a surprise, as just a week earlier, I was working on an iterative version of the function nested_depth(L). I will present it here:

def nested_depth(L: list) -> int:
    '''Return the maximum depth of nested lists L. Does not work on infinitely
    nested list.
    
    >>> nested_depth(1)
    0
    >>> nested_depth([1])
    1
    >>> nested_depth([1, 2])
    1
    >>> nested_depth([[1, 2], 3])
    2
    >>> nested_depth([[1, 2], [[3]]])
    3
    >>> nested_depth([[[[1]], [2]], [2]])
    4
    >>> nested_depth([[1], 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]])
    5
    >>> nested_depth([0, [1, [2, [0]], [3, [4, [[5]]]], 5], 6, 7])
    6
    >>> nested_depth([[3, 6, [2, [3, [[9, [1, 0, 7], 6], 8, 1], 9], 7]], 9, 4])
    7
    >>> nested_depth([0, [[1], [2, [0]], [3, [4, [[[[5]]]]]], 6], [7], [[8]]])
    8
    >>> nested_depth([1, 1, 1, 1, 1, [1], [1], [1], [1], [[1]]])
    3
    >>> nested_depth([1, 1, 1, 1, 1, [[1]], [[1]], [[1]], [[1]], 1])
    3
    '''
    # All non-lists have depth of 0
    if isinstance(L, list):
        # We keep track of two things: A dictionary to record the maximum
        # depth we reached; and a copy of the current list where we iteratively
        # append inner nested lists (as opposed to recursively.)
        max_depths = {}
        todo = L[:]
        
        for item in todo:
            if isinstance(item, list):
                # All the inner lists are appended to the end of todo
                for inner in item:
                    todo.append(inner)
                    
                    # The depth that we have currently reached is equivalent
                    # to the depth of the last item + 1
                    try:
                        max_depths[id(inner)] = max_depths[id(item)] + 1
                    except KeyError:
                        # If there was no last item, then we have just started
                        # at depth 2
                        max_depths[id(inner)] = 2

        # Since we record max_depths starting at depth 2 (a loop inside a list)
        # if the dictionary is empty then the depth is only 1
        return max(max_depths.values()) if len(max_depths) > 0 else 1
    else:
        return 0

As a reminder, the original nested_depth(L) function given in class was a 1 line function that returned the maximum depth of nested lists L. It is as follow:

def nested_depth (L):
 return (1 + max ([nested_depth (x) for x in L] + [0]) 
   if isinstance (L, list) else 0)

The idea behind my algorithm is to iterate through a list "todo" which begins as a copy of "L". However, every time a list nested inside "L" is reached, its content is appended to "todo" so that it will be analyzed later on in the iteration.

In the meantime, a dictionary "max_depths​" is used to keep track of the deepest list that we have discovered through the above process. In this dictionary, the key is the id of an object, and the value is the depth of that object. Every time a list's content is appended via the above process, each item is put into the max_depths​ dictionary with their id as the key. The value of of each item is determined by taking the value of the shallower list stored in the dictionary (i. e. the value in the dictionary of the list this item belongs to), and adding 1 to it. If a KeyError is returned, then it means there are no other lists that this item belongs to, meaning this is the first nested list with a depth of 2. The maximum nested depth can be determined simply by finding the maximum value in the dictionary "max_depths". If "max_depths" is empty, then there are no nested lists, so the nested depth is 1.

This algorithm works because it takes the idea of recursion, and convert it to iteration. Appending nested list to the end of "todo" while iterating through it is similar to recursion. The returned value of each would-be recursive call is stored in the format of a dictionary, as opposed to being returned.

While this shows that a recursive function can indeed be done with iteration, it is nonetheless very long and cumbersome. Similarly, a few years ago I ended up developing an iterative (although not in-place) version of Merge Sort as I did not have the knowledge of recursion back then. It took me several days of drafting, but our professor was able to complete it with 1 line and 1 helper function. In the end, the moral of recursion isn't that we must use it. Rather, it is simply much easier to use in many cases.