How to go through the several lists with recursion

Question

So I have this code which counts the number of symbols in lists with for cycle, which is not recursion

def cnt_same(l: list, pos=None, res=None) -> dict:
    if res is None and pos is None:
        res = {}
        pos = 1
    for i in l:
        if not type(i) == list:
            res[i] = res.get(i, 0) + pos
        else:
            cnt_same(i, pos, res)
    return res

output:

print(cnt_same([[], [], [], [], ["h", "h", "m"], [], ["m", "m", "M", "m"]])) # {'h': 2, 'm': 4, 'M': 1}
print(cnt_same([]))  # {}
print(cnt_same([['a'], 'b', ['a', ['b']]]))  # {'a': 2, 'b': 2}

How to turn this code into a recursive solution in which the passage through the lists is done by recursion?

Possible duplicate of [Nested List and count()](https://stackoverflow.com/questions/5828123/nested-list-and-count) — alex, Nov 04 '19 at 12:11

score 1 · Accepted Answer · answered Nov 04 '19 at 12:32

I think you just wish to convert the for loop to recursions. If so,

first, add a check to see if l is empty and if it is empty, return an empty dictionary.

if not l:
    return {}

Now do what has already been done

if res is None and pos is None:
    res = {}
    pos = 1

Now manually get the first element in l and store in i.

i = l[0]

Then copy from original program

if not type(i) == list:
    res[i] = res.get(i, 0) + pos
else:
    cnt_same(i, pos, res)

Now the recursive call with all elements of l except the first, which has already been processed.

cnt_same(l[1:], pos, res)

And finally, return res.

return res

So, the final thing would be something like

def cnt_same(l: list, pos=None, res=None) -> dict:
    if not l:
        return {}

    if res is None and pos is None:
        res = {}
        pos = 1

    i = l[0]
    if not type(i) == list:
        res[i] = res.get(i, 0) + pos
    else:
        cnt_same(i, pos, res)
    cnt_same(l[1:], pos, res)
    return res

Seems better to do: `if not res anf not pos:` and also `if not isinstance(i, list):` — Max Voitko, Nov 04 '19 at 12:37

score 0 · Answer 2 · answered Nov 04 '19 at 12:42

I suggest you the following way to do, which is quite easy to read and short:

def cnt_same(myList, d=None, start=True):
    # Initialize the dictionary (only on first call)
    if start:
        d = dict()
    # Iterate over the elements of the list
    for element in myList:
        if isinstance(element, list):
            # Here: the element is a list: RECURSION
            cnt_same(element, d, start=False)
        else:
            # Here: the element is NOT a list: count it
            d[element] = d.get(element, 0) + 1
    return d


d = cnt_same([[], [], [], [], ["h", "h", "m"], [], ["m", "m", "M", "m"]])
print(d) # {'h': 2, 'm': 4, 'M': 1}

d = cnt_same([])
print(d) # {}

d = cnt_same([['a'], 'b', ['a', ['b']]])
print(d) # {'a': 2, 'b': 2}

How to go through the several lists with recursion

2 Answers2