How to create a recursive algorithm to find the depth of a list

Question

I’m trying to create a recursive algorithm to find the depth of a list, which is the largest number of nested lists, But this is complicated, I can’t find it. I understand the path that the algorithm has to take, but I still don’t understand clearly how to do it and how to implement it. If someone could help me understand better how to do it, it would be cool.

What I’ve realized so far is that every time an element is a list, we have to increase a counter variable, but I’m not sure how to relate this variable to recursive calls.

I would like to know the process to reach the solution and not a solution, because then I would understand better how recursion works...

I’ve seen some recursive solutions on stackoverflow, as for example this:

def flat(l):
    depths = []
    for item in l:
        if isinstance(item, list):
            depths.append(flat(item))
    if len(depths) > 0:
        return 1 + max(depths)
    return 1

But still it is not easy to understand why of all the calls and all the steps...

Answer 1

Recursion with theoretical explanation is even more difficult to understand, so let’s see in practice:

count = 0
def flat(l):
    global count
    count += 1
    depths = []
    print "- entrando em for, flat n:", count
    for item in l:
        print item
        if isinstance(item, list):
            print "- e lista, entramos em recursao..."
            print "depths.append(flat(", item, "))"
            depths.append(flat(item))
    print "- saindo de for, chamada flat n: ", count
    count -= 1
    if len(depths) > 0:
        print "- depths: ", depths, "retorno de 1 +", max(depths)
        return 1 + max(depths)
    print "- retornamos 1, pois depths esta vazia"
    return 1

print flat(["A", ["B", ["C", ["D"]]]])

To flat([1, [2]]) it’s like we had:

flat([1, 
   flat([2]) 
])

After running the program, you will understand how the implementation works.

I have this code that I did a long time ago, in it you can see the same, only it returns a new list with all the elements (one more implementation so you can analyze):

def return_all_items(i_list, end_list):
    for value in i_list:
        if isinstance(value, list):
            return_all_items(value, end_list)
        else:
            end_list.append(value)

>> lists_in_list = [["A", ["B"]], "C", "D", ["E", "F"]]
>> list_results = []
>> return_all_items(lists_in_list, list_results)
>> list_results
['A', 'B', 'C', 'D', 'E', 'F']

Answer 2

I think the best way to understand this is to think from the bottom up.

For example:

arvore1 = [ 1, 2]
profundidade1 = 1

arvore2 = [ 4, 5]
profundidade2 = 1

arvore3 = [ 3, [ 1, 2]]
profundidade3 = 1 + profundidade1

arvore4 = [ 3, [1, 2], [ 4, 5]]
profundidade4 = 1 + max(profundidade1, profundidade2)

So we can say that the maximum depth of a tree is equal to 1 + the greatest depth of subtrees.