Как пройти через несколько списков с рекурсией

Question

Итак, у меня есть этот код, который подсчитывает количество символов в списках для цикла, который не является рекурсией

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

вывод:

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}

Как превратить этот код врекурсивное решение, при котором проход по спискам осуществляется рекурсией?

Answer 1

Я думаю, вы просто хотите преобразовать цикл for в рекурсии. Если это так, сначала

, добавьте проверку, чтобы убедиться, что l пусто, а если пусто, верните пустой словарь.

if not l:
    return {}

Теперь сделайте то, что уже сделано

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

Теперь вручную получите первый элемент в l и сохраните в i.

i = l[0]

Затем скопируйте из исходной программы

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

Теперьрекурсивный вызов со всеми элементами l, кроме первого, который уже обработан.

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

И, наконец, возврат res.

return res

Итак, последнеебудет что-то вроде

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

Answer 2

Я предлагаю вам следующий способ, который довольно легко прочитать и кратко:

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}