Python Recursive Example Explanation

Question

So currently working through MIT's OpenCourseWare computer science course online and I am having trouble trying to understand one of the recursive examples.

def f(L):
    result = []
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            return f(e)
return result

When the following input is given:

print f([1, [[2, 'a'], ['a','b']], (3, 4)])

The output is:

[2, 'a']

I am having trouble trying to understand how this function actually works or what it is doing. Shouldn't the function eventually be adding every string or int into the result list? I just need help with trying to understand how this function "winds up" and "unwinds"

I feel like the output should be:

[1,2,'a','a','b',3,4]

Any help would be appreciated thanks!

Answer 1

The function f returns a (shallow) copy of the first flat list it encounters with depth first search.

Why? Well first let us take a look at the base case: a list that contains no lists. Like [1,'a',2,5]. In that case the the if statement will always succeed, and therefore all elements of e will be added to the result and the result is returned.

Now what about the recursive case. This means there is an element that is a list. Like for instance [1,['a',2],5]. Now for the first element, the if succeeds, so 1 is added to the result list. But for the second element ['a',2] the if fails. This means we perform a recursive call on f with ['a',2]. Now since that list does not contain any sublists, we know it will return a copy of that list.

Note however that we immediately return the result of that recursive call. So from the moment we take the else branch, the result is of no importance anymore: we will return what that f(e) returns.

If we make the assumption we cannot construct a loop of infinite deep sublists (actually we can, but in that case we will get a stack overflow exception), we will eventually obtain a flat list and obtain that copy.

Example: If we take your sample input [1, [[2, 'a'], ['a','b']], (3, 4)]. We can trace the calls. So we first call f on that list, it will generate the following "trace":

# **trace** of an example function call
f([1, [[2, 'a'], ['a','b']], (3, 4)]):
    result = []
    # for 1 in L:
    # if type(1) == list: # fails
    # else
    result.append(1) # result is now [1]
    # for [[2,'a'],['a','b']] in L:
    # if type([[2,'a'],['a','b']]) == list: succeeds
    return f([[2,'a'],['a','b']])
                      result = []
                      # for [2,'a'] in L:
                      # if type([2,'a']) == list: succeeds
                      return f([2,'a'])
                                        result = []
                                        # for 2 in L:
                                        # if type(2) == list: fails
                                        # else:
                                        result.append(2) # result is now [2]
                                        # for 'a' in [2,'a']:
                                        # if type('a') == list: fails
                                        # else:
                                        result.append('a') # result is now [2,'a']
                                        return [2,'a']
                      return [2,'a']
    return [2,'a']

Flattening:

Given you wanted to flatten the list instead of returning the first flat list, you can rewrite the code to:

def f(L):
    result = []
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            result += f(e)
    return result

Note that this will only flatten lists (and not even subclasses of lists).

Answer 2

so by your suggested answer I see that you understand about the idea of the code. It digs deeper and deeper until it finds an element. But look about the back-step to the upper levels:

When it reaches the deepest point for the first time (the elements of the [2,'a'] list) it finish the loop on this level and returns the results 2 and a. And here is a RETURN statement ... that means the loop is stoped and thus no other elements are found.

The open question is now, why it is not showing 1 as part of result ? For the same reason, the RETURN is the result of the lower levels (2,a) and the result of the upper level. If you change "result" to a global variable, the outcome will be [1, 2, 'a']

best regards

Answer 3

The function as posted returns/exits when running into a first bottom-down list-element which doesn't contain a list - this prevents walking all the further branches of the recursion. For example:

print( f([1, [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)]) )
# gives: [4, 'c']
print( f([1, ['X','Y'], [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)]) )
# gives: ['X','Y']

The key point causing this behaviour is the line

result = [] 

This resets the list with results on each call of the function to an empty list. This way only one item is returned up from the chain of the recursion calls.

By the way the function f below does what you have expected, doesn't it?

def f(L, result):
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            f(e, result)

result=[]; f([1, [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)], result) print( result )
# gives: [1, 2, 'a', 3, 'b', 4, 'c', 'a', 'b', (3, 4)]
result=[]; f( [1, ['X','Y'], [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)], result); print( result )
# gives: [1, 'X', 'Y', 2, 'a', 3, 'b', 4, 'c', 'a', 'b', (3, 4)]

NOTICE: (3,4) is a TUPLE not a list ...

The function f as above collects items from a list if these items are not a list themselves. In the special case, when the item in the list is a list, the function calls itself to collect the items from this list. This way all they way down of the hierarchy every element is collected, no matter how deep one needs to dig down. This is the beauty of recursion - a function calling itself does the 'magic' of visiting all of the branches and their leaves down a tree :)