Python - Рекурсия

Рекурсия позволяет функции вызывать саму себя. Фиксированные шаги кода выполняются снова и снова для новых значений. Мы также должны установить критерии для принятия решения о завершении рекурсивного вызова. В приведенном ниже примере мы видим рекурсивный подход к двоичному поиску. Мы берем отсортированный список и передаем его диапазон индексов в качестве входных данных рекурсивной функции.

Двоичный поиск с использованием рекурсии

Мы реализуем алгоритм двоичного поиска с использованием Python, как показано ниже. Мы используем упорядоченный список элементов и разрабатываем рекурсивную функцию, которая принимает список вместе с начальным и конечным индексами в качестве входных данных. Затем функция бинарного поиска вызывает себя до тех пор, пока не найдет искомый элемент или не сделает вывод о его отсутствии в списке.

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

Когда приведенный выше код выполняется, он дает следующий результат:

2
None