Блог

Главная - Вопросы по программированию - кто-нибудь может помочь? Я хочу преобразовать этот цикл for в рекурсивную версию

кто-нибудь может помочь? Я хочу преобразовать этот цикл for в рекурсивную версию

#python #recursion

#python #рекурсия

Вопрос:

 G = [[0, 1, 1, 0, 0], [1, 0, 1, 1, 0], [1, 1, 0, 0, 1], [0, 1, 0, 0, 1], [0, 0, 1, 1, 0]]


def IsDominate(A, S, v):
    for i in range(0, len(A)):
        vert = S[i]
        if (A[vert][v] == 1):
            return True
    return False

print(IsDominate(G, [0, 3, 2], 1))

В основном функция принимает в качестве входных данных матрицу смежности A графа G, подмножество S его вершин и вершину v. Функция возвращает true, если S доминирует над v и false в противном случае.

Вот мой неправильный код, использующий рекурсию:

 def ISDominate(A, S, v, i):
    if i == 0:
        return A[0]
    vert = S[i]
    if (A[vert][v] == 1):
        return True
    return IsDominate(A,S, v, i-1)

print(ISDominate(G, [0, 2, 3], 1, len(G)-1))

Комментарии:

1. вы смотрели на numpy? или вы действительно хотите сделать это самостоятельно?

2. @user3732793 Нет, я не смотрел на Numpy

Ответ №1:

Прежде всего, ваш код выдает ошибку IndexError при задании этого графика смежности:

 G = [[0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 1], 
     [0, 0, 1, 1, 0]]

Это потому, что длина S меньше длины G. Когда он не может вернуть True, он в конечном итоге выходит за пределы индекса.

Чтобы сделать ваш код рекурсивным, вы можете сделать это:

 G = [[0, 1, 1, 0, 0], 
     [1, 0, 1, 1, 0], 
     [1, 1, 0, 0, 1], 
     [0, 1, 0, 0, 1], 
     [0, 0, 1, 1, 0]]

def IsDominate(A, S, v):
    if A[S[0]][v] == 1:
            return True
    return IsDominate(A,S[1:],v) if S[1:] else False

print(IsDominate(G, [0, 3, 2], 1))

В основном проверьте первую запись и вызовите функцию рекурсивно без первой записи S. Я не рекомендую использовать рекурсию здесь, на мой взгляд, это не добавляет эффективности или удобочитаемости.