Рекурсия

Как мы уже много раз видели, функции могут вызывать другие функции. Например:

def hello(name : str):
    print("Hello", name)

def hello_many_times(name : str, times : int):
    for i in range(times):
        hello(name)

Функция также может вызывать саму себя, но нам как программистам нужно быть осторожными, когда мы это делаем. Легко попасть в бесконечный цикл вызовов функций, так же как мы попадали в бесконечный цикл повторений с циклами while, если оставляли без внимания подходящие условия остановки. Поэтому попытка вызвать функцию hello со следующим определением

def hello(name : str):
    print("Hello", name)
    hello(name) # function calls itself

привела бы к новому виду ошибки:

Что означает рекурсия?

Рекурсия, упомянутая в ошибке выше, означает определение чего-либо через само себя. В контексте программирования это обычно относится к функции, которая вызывает саму себя. Чтобы это работало без бесконечных циклов, аргументы, передаваемые функции, должны каждый раз изменяться, так чтобы вложенные вызовы функций в какой-то момент остановились. Базовый принцип здесь такой же, как в циклах while: всегда должно быть какое-то условие остановки, и это условие должно в какой-то момент сработать.

Рассмотрим простую функцию, которая добавляет нули в список, пока в списке меньше 10 элементов. Однако на этот раз мы не используем цикл. Если условие еще не выполнено, функция вызывает саму себя:

def fill_list(numbers: list):
    """ If the length of the list is less than 10, add items to the list """
    if len(numbers) < 10:
        numbers.append(0)
        # call the function again
        fill_list(numbers)


if __name__ == "__main__":
    test_list = [1,2,3,4]
    fill_list(test_list)
    print(test_list)

Этой же функциональности можно было бы добиться с обычным циклом while:

def fill_list(numbers: list):
    """ If the length of the list is less than 10, add items to the list """
    while len(numbers) < 10:
        numbers.append(0)

if __name__ == "__main__":
    test_list = [1,2,3,4]
    fill_list(test_list)
    print(test_list)

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

Рекурсия и возвращаемые значения

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

def factorial(n: int):
    """ The function calculates the factorial n! for n >= 0 """
    if n < 2:
        # The factorial for 0 and 1 is 1
        return 1

    # Call the function again with an argument that is one smaller
    return n * factorial(n - 1)

if __name__ == "__main__":
    # Tesing our function
    for i in range(1, 7):
        print(f"The factorial of {i} is {factorial(i)}")

Если параметр рекурсивной функции factorial равен 0 или 1, функция возвращает 1, потому что именно так определена операция факториала. Во всех остальных случаях функция возвращает значение n * factorial(n - 1), то есть значение своего параметра n, умноженное на возвращаемое значение вызова функции factorial(n - 1).

Ключевая часть здесь в том, что определение функции содержит условие остановки. Если оно выполнено, рекурсия заканчивается. В этом случае условие — n < 2. Мы знаем, что оно в итоге будет достигнуто, потому что значение, передаваемое функции как аргумент, уменьшается на один на каждом уровне рекурсии.

Инструмент визуализации может очень помочь в понимании рекурсивных программ.

Пример выше может стать немного понятнее, если использовать вспомогательные переменные:

def factorial(n: int):
    if n < 2:
        return 1

    factorial_one_level_down = factorial(n - 1)
    factorial_now = n * factorial_one_level_down
    return factorial_now
    
factorial(5)

Посмотрите, как инструмент визуализации демонстрирует ход рекурсии.

У инструмента визуализации есть небольшая особенность в том, как он обрабатывает стек вызовов: он как будто "растет" вниз. Обычно стеки вызовов изображают именно как стеки, где новые вызовы помещаются сверху. В инструменте визуализации текущий активный вызов функции — это затемненный блок внизу, в котором видны собственные копии переменных.

Когда вызывается рекурсивная функция factorial, стек вызовов строится до тех пор, пока не будет достигнут предел, заданный n < 2. Затем последний вызов функции в стеке возвращает значение — это 1, так как n теперь меньше 2. Это возвращаемое значение передается предыдущему вызову функции в стеке, где используется для вычисления возвращаемого значения этого вызова, и так далее обратно из стека.

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

Рассмотрим еще один распространенный рекурсивный пример: число Фибоначчи. В последовательности Фибоначчи каждое число является суммой двух предыдущих чисел. Первые два числа здесь определены как 1 и 1, и последовательность начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34.

def fibonacci(n: int):
    """ The function returns the nth number in the Fibonacci sequence (1, 1, 2, 3, 5, 8 etc.); n > 0"""

    if n <= 2:
        # the first two are ones
        return 1

    # All other numbers equal the sum of the two preceding numbers in the sequence
    return fibonacci(n - 1) + fibonacci(n - 2)

# Test that everything works
if __name__ == "__main__":
    for i in range(1, 11):
        print(f"The {i}. number in the Fibonacci sequence is {fibonacci(i)}")

На этот раз условие остановки состоит в том, что параметр меньше или равен 2, потому что вся последовательность определяется начиная с первых двух чисел, а первые два числа мы определили равными 1.

Итак, как эта функция работает на практике?

Если функция вызывается с аргументом 1 или 2, она возвращает 1, как задано условием n <= 2.

Если аргумент равен 3 или больше, функция возвращает значение fibonacci(n - 1) + fibonacci(n - 2). Если аргумент ровно 3, это значение равно fibonacci(2) + fibonacci(1), а результат обоих этих вызовов нам уже известен из предыдущего шага. 1 + 1 равно 2, что действительно является третьим числом последовательности Фибоначчи.

Если аргумент равен 4, возвращаемое значение - fibonacci(3) + fibonacci(2), что, как мы теперь знаем, равно 2 + 1, то есть 3.

Если аргумент равен 5, возвращаемое значение - fibonacci(4) + fibonacci(3), что, как мы теперь знаем, равно 3 + 2, то есть 5.

И так далее, и так далее.

Мы можем на каждом шаге убедиться, что функция дает правильные результаты, и этого часто достаточно в базовых задачах программирования. Формальная проверяемость алгоритмов - тема более продвинутых курсов, таких как Data Structures and Algorithms.

Бинарный поиск

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

Идея бинарного поиска состоит в том, чтобы всегда смотреть на элемент в самом центре списка. Затем есть три возможных сценария. Если элемент в центре

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

Если список пуст, мы можем определить, что элемент не найден, и вернуть соответствующий признак.

На следующем изображении видно, как бинарный поиск продвигается при поиске числа 24:

Вот рекурсивный алгоритм бинарного поиска:

def binary_search(target: list, item: int, left : int, right : int):
    """ The function returns True if the item is contained in the target list, False otherwise """
    # If the search area is empty, item was not found
    if left > right:
        return False

    # Calculate the centre of the search area, integer result
    centre = (left+right)//2

    # If the item is found at the centre, return
    if target[centre] == item:
        return True

    # If the item is greater, search the greater half
    if target[centre] < item:
        return binary_search(target, item, centre+1, right)
    # Else the item is smaller, search the smaller half
    else:
        return binary_search(target, item, left, centre-1)


if __name__ == "__main__":
    # Test your function
    target = [1, 2, 4, 5, 7, 8, 11, 13, 14, 18]
    print(binary_search(target, 2, 0, len(target)-1))
    print(binary_search(target, 13, 0, len(target)-1))
    print(binary_search(target, 6, 0, len(target)-1))
    print(binary_search(target, 15, 0, len(target)-1))

Функция binary_search принимает четыре аргумента: целевой список, искомый элемент, левую и правую границы области поиска. При первом вызове функции область поиска охватывает весь целевой список. Левая граница находится на индексе 0, а правая - на индексе len(target)-1. Функция вычисляет центральный индекс и проверяет эту позицию в списке. Либо элемент найден, либо поиск продолжается в меньшей или большей половине целевого списка.

Сравним это с простым линейным поиском. При линейном поиске область поиска проходится с начала, пока элемент не будет найден или пока область поиска не закончится. Количество шагов, необходимых для охвата всей области поиска, растет линейно с тем же темпом, что и размер области поиска. Каждый шаг поиска покрывает только одного кандидата с начала области поиска. Предположим, искомый элемент не найден. Если область поиска содержит миллион элементов, пришлось бы сделать миллион шагов поиска, чтобы убедиться, что элемента нет в области поиска.

В бинарном поиске, напротив, количество необходимых шагов растет логарифмически. Снова предположим, что искомый элемент не найден. Область поиска делится пополам на каждом шаге, потому что мы знаем, что элемент либо меньше, либо больше текущего кандидата в центре. 2 в степени 20 (2^20) уже значительно больше 1 миллиона, поэтому для охвата всей области поиска бинарным поиском потребуется не больше 20 шагов. Поэтому, когда мы имеем дело с отсортированными областями поиска, как это часто бывает при работе с компьютерами и материалами, предназначенными для автоматической обработки, бинарный поиск гораздо эффективнее линейного.

Текущие баллы можно посмотреть в синем индикаторе в правом нижнем углу страницы.