рекурсия по неправильной матрице не может найти результат - PullRequest
Новая
       6

рекурсия по неправильной матрице не может найти результат

0 голосов
/ 11 апреля 2020

Я хотел немного попрактиковаться в рекурсии и подумал, что поиск в нерегулярных матрицах будет увлекательным занятием. У меня есть эта простая рекурсия, которая работает, но почему-то не завершает весь массив. Он не может найти номера 8-11. Он должен возвращать координаты, где совпадение, чтобы я мог работать с ним позже. Я что-то упускаю? 


array = [
    [1, 2, [3, 4, [5, [6, [7, 0]]]], [8, 9], 10, 11]
    ]

def searchArray(array, searched, coordinates=[]):
    for i, dimension in enumerate(array):
        if type(dimension) == int:
            if dimension == searched:
                return coordinates+[i,]
        else:
            coordinates.append(i)
            return searchArray(dimension, searched, coordinates=coordinates)

searched = 5
coordinates = searchArray(array, searched)
print(coordinates)

1 Ответ

1 голос
/ 11 апреля 2020

Проблема в том, что вы возвращаетесь из функции, как только вы делаете рекурсивный вызов во вложенном списке, независимо от того, найден он или нет searched. Таким образом, for l oop никогда не продолжает искать в оставшейся части списка.

Вам необходимо проверить, была ли рекурсия успешной, прежде чем вернуться.

Кроме того, вам не следует изменять coordinates на месте с append(). В конечном итоге вы получите список всех координат, в которые вы спустились, независимо от того, была ли она успешной. Передайте новый список в качестве аргумента в рекурсии. 

def searchArray(array, searched, coordinates=[]):
    for i, dimension in enumerate(array):
        if type(dimension) == int:
            if dimension == searched:
                return coordinates+[i,]
        else:
            found = searchArray(dimension, searched, coordinates=coordinates + [i])
            if found:
                return found
    return None # Not found
...