Рекурсия в Python

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

factorial(5) = 120
factorial(3) = 6
factorial(7) = 5040

Сначала сделаем это с помощью цикла:

def factorial(number):
    x = 1
    for i in range(1, number+1):
        x *= i
    return x

factorial(5) #returns 120

И теперь решение с помощью рекурсивной функции:

def factorial(number):
    if number == 1:
        return 1
    return number * factorial(number - 1)

factorial(5) #returns 120

Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы, а наоборот, может ее замедлить. Но рекурсия делает код более понятным для программиста и в такой код проще вносить изменения.

Стек вызовов

Для понимая того как работают рекурсивные функции, нужно понимать, что такое стек вызовов.

В каждой программе есть специальный стек, в котором сохраняется информация о вызовах функций. Он называется стек вызовов и именно с его помощью программа запоминает, куда она должна вернуться и ещё множество других вещей. Стеки работает по принципу LIFO (last in, first out).

Стек вызовов работает так:

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

Когда вы вызываете функцию из функции, вызывающая функция временно приостанавливается в частично завершенном состоянии.

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

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

Рекурсивный и базовый случаи

Так как рекурсивная функция вызывает саму себя, то достаточно легко ошибиться и сделать такой вызов бесконечным 🙂

P.S. На самом деле бесконечным он не будет, так как рано или поздно переполниться стек. Но если что-то пошло не так нажмите в терминале Ctrl (Cmd) + C.

Итак, рекурсия всегда делится на базовый и рекурсивный случаи.

Когда вы пишите рекурсивную функцию, то обязательно нужно указать случай, когда рекурсия должна прерваться — это и есть базовый случай.

Рекурсивный случай отвечает за рекурсию и приведению к базовому случаю.

Вернемся к примеру с вычислением факториала:

def factorial(number):
    if number == 1:
        return 1
    return number * factorial(number - 1)

Здесь за базовый случай отвечает кусок кода:

if number == 1:
        return 1

А за рекурсивный:

return number * factorial(number - 1)

В рекурсивном случае мы на каждом новом вызове функции уменьшаем значение number и тем самым, с каждым шагом, становимся всё ближе к базовому случаю. Если бы на последней строке мы указали return number * factorial(number), то функция бы зависла, так как значение number оставалось бы неизменным.

Примеры

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

Функция sum_numbers

Для начала нам нужно определить базовый и рекурсивный случай.
Базовым случаем здесь может быть пустой массив или массив из одного элемента. В случае с пустым массивом нам нужно будет вернуть 0, а с одним элементом — его значение. Я буду придерживаться того, что базовый случай это пустой массив.

def sum_numbers(numbers):
    if len(numbers) == 0:
        return 0
    return numbers[0] + sum_numbers(numbers[1:])

Выше в коде происходит следующее:

1. В блоке if проверяем длину массива и если она равна нулю, то возвращаем ноль.
2. В рекурсивном случае я возвращаю первый элемент массива и прибавляю к нему результат вызова функции в которую уже передаются оставшиеся элементы массива, начиная с первой позиции.
3. По мере углубления рекурсии мы будем передавать массив всё меньшей длины, пока массив не окажется пустым.

Вот как это выглядит при визуализации на pythontutor.com

Важно отметить, что этот пример академический и его не стоит использовать в работе, т.к. в питоне есть встроенная функция sum().

Поиск наибольшего числа в массиве

def get_max_value(numbers):
    if len(numbers) == 2:
        if numbers[0] > numbers[1]:
            return numbers[0]
        else:
            return numbers[1]
    max_value = get_max_value(numbers[1:])

    if numbers[0] > max_value:
        return numbers[0]
    else:
        return max_value

Тут нужно понять следующее — с помощью рекурсии мы сокращаем наш массив до базового случая, когда остается всего лишь два числа. Эти числа мы сравниваем между собой и возвращаем наибольшее число из двух.
В max_value на «обратном проходе» сначала сохранится результат сравнения двух последних чисел массива, далее в последнем блоке if мы будем сравнивать что больше — текушее максимальное значение или первый элемент массива, который сейчас в блоке стека.

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

def get_max_value(numbers):
    max_value = 0
    for number in numbers:
        if number > max_value:
            max_value = number
    return max_value

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

def bin_search(target, numbers, left_position, right_position):
    if right_position <= left_position:
        return -1

    mid_position = (left_position + right_position) // 2

    if target == numbers[mid_position]:
        return mid_position
    elif numbers[mid_position] > target:
        return bin_search(target, numbers, left_position, mid_position)
    else:
        return bin_search(target, numbers, mid_position + 1, right_position)

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

Далее по алгоритму:

1. Если правая позиция меньше или равна левой — значит алгоритм не нашел нужного элемента и мы возвращаем -1.
2. Определяем средний элемент.
3. Если находим нужное число, то возвращаем его индекс.
4. Если значение среднего элемента больше целевого, то начинаем искать в правой части массива.
5. Если средний элемент меньше целевого, то ищем в левой части.

На каждом проходе значение mid_position сдвигается правее или левее, но сам массив остается неизменным.