Чтобы понять рекурсию, нужно понять рекурсию. В этой шутке — вся суть понятия, но попробуем всё-таки разобрать его подробно.
Что такое рекурсия в программировании
Рекурсия — это функция, которая вызывает саму себя. Представим, что есть функция А, которая выполняет определённое действие, — например, перемножает два значения. Внутри этой функции А в качестве одного из значений для умножения возьмём ту же самую функцию А. Получается, что функция умножает число на саму себя и внутри ещё раз умножает число на саму себя и так далее, до бесконечности или выполнения определённого условия.
Внутри кода это может выглядеть так:
func А (x) => x * A(x-1)
Понятие рекурсии используется только в программировании и иногда в мемах
Иногда рекурсия бывает косвенной. Например, функция А вызывает функцию В, а В — А. В итоге из А всё равно возвращаемся к А, хотя напрямую вызова самой себя в функции не происходит.
Пример косвенной рекурсии с сайта Lurkmore
Рекурсия функции нужна, когда требуется выполнить последовательность из одинаковых действий. Прописывать их все слишком долго, а иногда невозможно, потому что неизвестно, сколько действий понадобится. Например, надо создать функцию, которая выводит на экран числа от N до 1. Но конечное N неизвестно, и нужно передавать каждый раз разное. Тут и поможет рекурсия — она каждый раз будет вызывать сама себя, уменьшая заданное N на один, пока не дойдёт до единицы.
Вот как будет выглядеть код такой функции на Python:
void A(n){
if(n>=1){
A(n-1);
print(n);
}
}
Если передать число 3, то она последовательно выведет 3, 2, 1. Внутри функции A также вызывают функцию A — это и есть рекурсия.
Рекурсия немного похожа на цикл, который тоже позволяет несколько раз повторить одно и то же действие. Но внутри цикла функция не вызывается, только прописываются различные условия. Например, тот же счётчик, что описали выше, в случае с циклом будет выглядеть так:
void A(n){
while n>=1:
print(n)
n = n-1
}
Любую рекурсивную функцию можно описать в виде цикла, так что теоретически рекурсии можно не использовать в коде вообще. Однако у них есть преимущества перед циклами.
Материал по теме:
Что такое парадигмы программирования и зачем они нужны
Плюсы и минусы рекурсивных функций
Принцип «Разделяй и властвуй» — самое популярное и частое применение для рекурсии. Декомпозиция, то есть разбиение любой задачи на более мелкие части, — основа, на которой строится принцип рекурсии:
1. Разделять.
Решать проблему напрямую, если она небольшая. В противном случае разделить задачу на меньшие подмножества той же проблемы.
2. Властвовать.
Решать меньшие задачи рекурсивно. Если подзадача достаточно мала, рекурсия не нужна и можно решить её напрямую.
3. Комбинировать.
Взять готовое решение для маленькой подзадачи и объединить с решением исходной проблемы.
Как только большая задача будет разбита на множество мелких частей, можно использовать параллельное программирование для их одновременного выполнения, ускоряя весь процесс решения. Такой подход является самым быстрым и простым способом увеличить скорость алгоритма и всей программы.
Как прервать рекурсию
Суть рекурсии такова, что она может вызывать сама себя вечно, никогда не заканчиваясь. Это называется бесконечной рекурсией, выйти из которой можно только принудительным закрытием программы.
Чтобы этого не случилось, нужно ещё в процессе написания кода создать условие выхода из рекурсии. Возьмём пример программы, описанный выше:
void A(n){
if(n>=1){
A(n-1);
print(n);
}
}
Здесь есть условие — if(n>=1). Только в этом случае функция продолжает вызывать саму себя и что-то выводит. Как только n становится меньше единицы, функция прекращается, и рекурсия останавливается.
Чтобы прервать рекурсию, нужно:
- Прописать условие выхода из рекурсии до повторного вызова функции, иначе это условие просто не успеет пройти проверку. Обычно условие прописывают с помощью конструкции if.
- Убедиться, что это условие будет достигнуто. Например, если прописать if(n>=1), но не вычитать из n единицу, а прибавлять её, условие никогда не наступит, и рекурсия станет бесконечной.
Если код запущен, но что-то пошло не так и код не останавливается из-за рекурсии, его нужно остановить принудительно. Способ сделать это зависит от среды, в которой запущен код. Например, в терминале Windows для этого обычно нужно нажать Ctrl+C на клавиатуре.
Примеры алгоритмов рекурсии в программировании
Рекурсию можно использовать, чтобы:
● посчитать количество определённых символов в строке;
● определить какое-то свойство числа, например чётность или простоту;
● вычислить произведение нескольких чисел, возведение в степень, факториал;
● найти длину списка;
● перевести число в другую систему счисления;
● определить максимальный или минимальный элемент списка;
● выполнить многие другие задачи, требующие повторения нескольких одинаковых действий.
Возьмём пример кода на Python — возведение числа x в степень y. Функция должна уметь принимать оба значения и возводить первое число в степень, равную второму числу.
Вот как будет выглядеть его псевдокод — упрощённый, более понятный для чтения:
def degree(x, y):
if (y == 0):
return 1
if (y == 1):
return (x)
# оставшиеся кейсы, когда степень > 1
if (y != 1):
return (x * degree(x, y - 1))
x = int(input("Введите число: "))
y = int(input("Введите его степень: "))
print("Результат возведения в степень равен:", degree(x, y))
Что здесь происходит:
- Проверка, не введён ли 0 как значение степени: в этом случае сразу выводится 1, так как любое число в степени 0 равно 1.
- Создание условие выхода из рекурсии: как только y достигает 1, умножение прекращается и возвращается x, поскольку любое число в степени 1 равно самому себе.
- Рекурсивное умножение x на само себя столько раз, сколько задано в переменной y.
- Вывод результата возведения в степень.
Ещё один пример — подсчёт длины коллекции. Вот как будет выглядеть его псевдокод:
def length(collection):
if not collection:
return 0
return 1 + length(collection[1:])
n = [1, 2, 3, 4, 5]
print("Длина коллекции равна: ")
print(length(n))
Что здесь происходит:
- Создание условия выхода из рекурсии — если длина коллекции равна нулю, работа функции прекращается.
- Создание счётчика — начинается с 1 и рекурсивно прибавляется к ней ещё по 1, что постепенно отрезает от коллекции по одному элементу. Это делается с помощью среза коллекции collection[1:].
- Создание коллекции n из 5 элементов. Здесь она задаётся фиксированно, но в реальном коде коллекция может пополняться постепенно, и её длину действительно понадобится посчитать.
- Вывод длины коллекции путём передачи списка в качестве аргумента функции.
- Получение результата 5.
В качестве примера рекурсии можно рассматривать и вывод чисел Фибоначчи, то есть последовательности, в которой каждое следующие число — сумма двух предыдущих. Для этого придётся вызывать в функции саму себя дважды:
def fibonacci(n):
if (n <= 1):
return n
else:
return (fibonacci(n-1) + fibonacci(n-2))
n = int(input("Введите число членов последовательности:"))
print("Последовательность Фибоначчи:")
for i in range(n):
print(fibonacci(i))
Что здесь происходит:
- Создание условия выхода из рекурсии — как только количество чисел в последовательности становится 1.
- Сложение введённого числа, уменьшенного на единицу, с введённым числом, уменьшенным на два.
- Запрос у пользователя, сколько чисел Фибоначчи он хочет получить.
- Запуск вывода в виде цикла до тех пор, пока счётчик i не достигнет значения n.
Совет от эксперта
Николай Федосеев
Если есть опасение переполнить память или замедлить программу, лучше избежать использования рекурсии. Но если цикл растянулся уже на несколько десятков строк и не планирует останавливаться, то можно попробовать заменить его рекурсией — вполне вероятно, что так код станет чище, компактнее, а возможно, даже быстрее.
Дайджест блога: ежемесячная подборка лучших статей от редакции
Читать также:
