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

Question

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

Navigation

#1 by (1 votes)
#2 by (0 votes)

1

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 not find it. I realize the path that the algorithm has to make, but I still have not clearly understood how it has to do and how to implement it. If anyone could help me figure out how to do it better, it would be cool.

What I 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 get the solution and not a solution, because then you would better understand how recursion works ...

I've seen some recursive solutions in stackoverflow , 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 even then it is not easy to understand why all calls and all steps ...

python-3.x

asked by anonymous 10.11.2014 / 00:02

2 answers

Autocomplete in a jTextfield - adapt class Doubts in using the dataExporter

score 1 · Answer 1

Recursion with theoretical explanation is even harder 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"]]]])

For flat([1, [2]]) it's as if we have:

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

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

I have this code I made a long time ago, in it you can see the same, only it returns a new list with all the elements (another implementation for you to 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']

score 0 · 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)

Then we can say that the maximum depth of a tree is equal to 1 + the greatest depth of the sub-trees.