having trouble understanding this code

Question

I just started learning recursion and I have an assignment to write a program that tells the nesting depth of a list. Well, I browsed around and found working code to do this, but I'm still having trouble understanding how it works. Here's the code:

def depth(L) :
    nesting = [] 
    for c in L:
        if type(c)  == type(nesting) :
            nesting.append(depth(c)) 
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

So naturally, I start to get confused at the line with the append that calls recursion. Does anyone have a simple way of explaining what's going on here? I'm not sure what is actually being appended, and going through it with test cases in my head isn't helping. Thanks!

edit: sorry if the formatting is poor, I typed this from my phone

Answer 1

Let me show it to you the easy way, change the code like this: (### are the new lines I added to your code so you can watch what is happening there)

def depth(L) :
    nesting = []
    for c in L:
        if type(c)  == type(nesting) :
            print 'nesting before append', nesting ###      
            nesting.append(depth(c))
            print 'nesting after append', nesting ###
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

Now lets make a list with the depth of three:

l=[[1,2,3],[1,2,[4]],'asdfg']

You can see our list has 3 element. one of them is a list, the other is a list which has another list in itself and the last one is a string. You can clearly see the depth of this list is 3 (i.e there are 2 lists nested together in the second element of the main list)

Lets run this code:

>>> depth(l)
nesting before append []
nesting after append [1]
nesting before append [1]
nesting before append []
nesting after append [1]
nesting after append [1, 2]
3

Piece of cake! this function appends 1 to the nesting. then if the element has also another list it appends 1 + maximum number in nesting which is the number of time function has been called itself. and if the element is a string, it skips it.

At the end, it returns the maximum number in the nesting which is the maximum number of times recursion happened, which is the number of time there is a list inside list in the main list, aka depth. In our case recursion happened twice for the second element + 1=3 as we expected.

If you still have problem getting it, try to add more print statements or other variables to the function and watch them carefully and eventually you'll get it.

Answer 2

So what this seems to be is a function that takes a list and calculates, as you put it, the nesting depth of it. nesting is a list, so what if type(c) == type(nesting) is saying is: if the item in list L is a list, run the function again and append it and when it runs the function again, it will do the same test until there are no more nested lists in list L and then return 1 + the max amount of nested lists because every list has a depth of 1.

Please tell me if any of this is unclear

Answer 3

Let's start with a couple of examples.

First, let's consider a list with only one level of depth. For Example, [1, 2, 3].

In the above list, the code starts with a call to depth() with L = [1, 2, 3]. It makes an empty list nesting. Iterates over all the elements of L i.e 1, 2, 3 and does not find a single element which passes the test type(c) == type(nesting). The check that len(nesting) > 0 fails and the code returns a 1, which is the depth of the list.

Next, let's take an example with a depth of 2, i.e [[1, 2], 3]. The function depth() is called with L = [[1, 2], 3] and an empty list nesting is created. The loop iterates over the 2 elements of L i.e [1, 2] , 3 and since type([1, 2]) == type(nesting), nesting.append(depth(c)) is called. Similar to the previous example, depth(c) i.e depth([1, 2]) returns a 1 and nesting now becomes [1]. After the execution of the loop, the code evaluates the test len(nesting) > 0 which results in True and 1 + max(nesting) which is 1 + 1 = 2 is returned.

Similarly, the code follows for the depth 3 and so on.

Hope this was helpful.

Answer 4

This algorithm visits the nested lists and adds one for each level of recursion. The call chain is like this:

depth([1, 2, [3, [4, 5], 6], 7]) =
    1 + depth([3, [4, 5], 6]) = 3
        1 + depth([4, 5]) = 2
            1

Since depth([4,5]) never enters the if type(c) == type(nesting) condition because no element is a list, it returns 1 from the outer return, which is the base case.

In the case where, for a given depth, you have more than one nested list, e.g. [1, [2, 3], [4, [5, 6]], both the max depth of [2,3]and [4, [5, 6]] are appended on a depth call, of which the max is returned by the inside return.