Рекурсия и работа со списками в Python

Question

Моя задача:

Напишите функцию, которая рекурсивно ищет в сложном объекте значение. Сложный объект — это будет список списков списков и т. д. Например, [1, 2, [3, 4, [5, [6, []]]]]. Функция должна рекурсивно заходить внутрь вложенных списков, а если это другой тип данных - игнорировать его.

Сделал функцию searchNum(), мой ввод searchNum([[], 2 ,[[]], 1],1) должен вывести 3

def searchNum(array, value):
    for i in array:
        if isinstance(i, list):
            if len(i) == 0:
                continue
            if isinstance(i, list):
                return (array.index(i), searchNum(i, value))
        if isinstance(i, int):
            if i == value:
                return array.index(i)
    return False


print(searchNum([[], 2 ,[[]], 1],1))

Программа заходит в список под индексом 2 и возвращает из него False и не идет дальше к нужному числу (1, индекс 3). Как идти дальше по списку, используя рекурсию?

Мой ответ:

def newSearch(array, value):
for idx, val in enumerate(array):
    if isinstance(val, list):
        if len(val) == 0:
            continue
        if newSearch(val, value) == False:
            continue
        else:
            return f'{idx}, {newSearch(val, value)}'
    if isinstance(val, int):
        if val == value:
            return f'{idx}'

return False

print(newSearch([[], 2 ,[[]], [0,[9, 1]]],1))

Результат:

Answer 1

У вас есть и ошибка и не оптимальность.

for i in array:
    ...
    array.index(i)

Зачем заново искать индекс элемента в списке, если вы можете узнать его сразу в момент перебора:

for idx, val in enumerate(array):

Также не совсем понятно, что вы собираетесь вернуть из функции:

return (array.index(i), searchNum(i, value))
...
return array.index(i)
...
return False

У вас 3 разных варианта, что может вернуться из этой функции:

кортеж из индекса и чего-то ещё
просто индекс
просто False

Определитесь - что именно вы хотите возвращать и в каких случаях? Сейчас это выглядит какой-то случайной мешаниной

Но главная ошибка тут:

if isinstance(i, list):
    return (array.index(i), searchNum(i, value))

При заходе в рекурсию вы не проверяете, что вернула функция searchNum, а просто пробрасываете её результат выше по стеку вызовов. Таким образом, если попался по дороге список, вы получите результат поиска в этом списке как окончательный результат работы функции, и не важно - был там найден элемент или нет. Нужно проверять результат вызова и делать возврат только если он был успешный, а если нет, то нужно позволить поиску продолжиться на данном уровне рекурсии:

if isinstance(i, list):
    ret = searchNum(i, value)
    if ... : # тут проверка, что ret хороший
        return ... # тут возврат в этом случае

Answer 2

Я предлагаю решать эту задачу так, он возвращает индекс первого найденного элемента

def searchNum(array, value, answer=""):
    index = 0
    one_iter_ans = ""
    for index, check in enumerate(array):
        one_iter_ans = str(index) + "."
        if isinstance(check, list):
            if len(check) == 0:
                continue
            tmp = searchNum(check, value, answer + one_iter_ans)
            if tmp:
                return tmp
        if isinstance(check, int):
            if check == value:
                return answer + one_iter_ans
    return False


print(searchNum([[2, [1]], 2 ,[[]], 1],1))

Answer 3

1   def searchNum(array, value):
2       for index, i in enumerate(array):  # проходим по всем элементам
3          if isinstance(i, list):  # элемент список?
4               if len(i) == 0:  # пустой?
5                   continue  # пропускаем, возвращаем -1
6               res = searchNum(i, value)  # если не пустой -> рекурсивным вызовом проверяем внутренний список
7               if isinstance(res, int) and res >= 0:  # результат вызова число больше нуля? (индекс)
8                   return str(index) + '.' + str(res)  # возвращаем индекс внутреннего списка, где мы нашли индекс элемента + dot + индекс искомого элемента
9           if isinstance(i, int):  # элемент число?
10              if i == value:  # которое нам нужно?
11                  return index  # возвращаем его
12  return False  # ничего не нашли? возвращаем False

[0, [0, 5]] ищем 5

При первой итерации цикла (i=0) попадаем в строку 10, результат False, ничего не делаем, берём следующий элемент. Следующий элемент - список i=[0,5], попадаем в строку 3, затем в 6, переходим на следующий уровень рекурсии

Снова проходимся по списку, первая итерация цикла (i=0), снова попадаем в строку 10, результат False, ничего не делаем берём следующий элемент (i=5), это тоже число, попадаем в строку 10, результат True, возвращаем индекс = 1

На предыдущем уровне мы остановились в строке 6 на элементе с индексом 1 (это индекс внутреннего списка), результат = 1, попадаем в строку 7, условие выполняется, выполняем возврат строки = 1(индекс) + . + найденный индекс(1) = 1.1, рекурсия закончена, значение вернулось конструкции, которая впервые вызвала метод, результат = 1.1

Если элемента в списке не окажется, метод всегда будет возвращать False, и результат, соответственно, тоже будет False

БЛОГ НА HUSL

Рекурсия и работа со списками в Python

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