Проблемы с рекурсией

Question

вот код который должен из многомерных списков сделать один список:

def one_level_flatten(value: list):
    filter_value = list(filter(lambda x: x is not [], value))
    flatten_values = list()
    for i in filter_value:
        if isinstance(i, list):
            for j in i:
                flatten_values.append(j)
        else:
            flatten_values.append(i)
    return flatten_values


def flatten(*args):
    sequence = [i for i in args]
    if list in list(map(type, sequence)):
        return flatten(one_level_flatten(sequence))
    else:
        return sequence

Это рекурсивная программа. Если честно, это задача с codewars.

Вопрос : почему мне выдает ошибку, что рекурсия сработала 992 раза, если максимальная многомерность списков в тесте не больше 5? В программе все проверки работают, и работа в рекурсией безопасна.

print(one_level_flatten([[], 11, 22, [], [1, 2, 3, [4, 5]]]))
print(one_level_flatten(one_level_flatten([[], 11, 22, [], [1, 2, 3, [4, 5]]])))

Результат функции one_level_flatten. То есть ошибка в функции flatten:

[11, 22, 1, 2, 3, [4, 5]]
[11, 22, 1, 2, 3, 4, 5]

Вот тесты с codewars

@test.describe('Example Tests')
def example_tests():
    test.assert_equals(flatten(),[])
    test.assert_equals(flatten(1,2,3),[1,2,3])
    test.assert_equals(flatten([1,2],[3,4,5],[6,[7],[[8]]]),[1,2,3,4,5,6,7,8])
    test.assert_equals(flatten(1,2,['9',[],[]],None),[1,2,'9',None])
    test.assert_equals(flatten(['hello',2,['text',[4,5]]],[[]],'[list]'),['hello',2,'text',4,5,'[list]'])

Вот ошыбка

Answer 1

Рассмотрим простой пример. Что вернёт вот это?

one_level_flatten([])

А оно вернёт []. Т.е. то же самое, что ей дали на вход. Соответственно, конструкция

def flatten(*args):
    sequence = [i for i in args]
    if list in list(map(type, sequence)):
        return flatten(one_level_flatten(sequence))

Будет крутиться бесконечно. Потому как на первой итерации sequence[0] равна '[]' и это list. На второй итерации эта переменная опять такая же, так что снова входит в рекурсию. И так до бесконечности.

Раз вы используете *args как список, то самый "плоский" список для функции flatten() будет просто аргументы. А самый "плоский" вид, который возвращает функция one_level_flatten() - это список. Соответственно, чтобы передать список как аргументы, надо просто использовать оператор разложения по аргументам *:

flatten(*one_level_flatten(sequence))

Ну и вообще, весь код в принципе вырождается в одну строчку :)

def flatten(*args):
    return flatten(*sum([i if isinstance(i, list) else [i] for i in args], [])) if list in list(map(type, args)) else list(args)

БЛОГ НА HUSL

Проблемы с рекурсией

Ответы (1 шт):