Рекурсия
Что такое рекурсия
Сейчас будет максимальная база. Рекурсия — это рекурсия. А если серьезно и чуть заумно, то:
Рекурсия — вариант поведения функции, при котором она в ходе своей работы вызывает сама себя.
На самом деле понятие используется много где, не только в информатике и программировании. Рекурсия встречается в физике, химии, биологии, и — внезапно! — даже в лингвистике.
К счастью, так широко нам разбираться не нужно, остановимся только на программировании.
В коде для разных языков программирования рекурсивные функции будут работать одинаково — вызывать сами себя и при этом работать «внутри» друг друга.
Реализовать такое поведение функций можно двумя способами:
- прямо;
- косвенно.
Прямая рекурсия вызывает сама себя. Вот так просто. Косвенная действует через посредника. Она сначала вызывает другую функцию, которая уже вызывает первую — круг замыкается.
Вот пропал куда-то телефон, вообще нет идей, где лежит. Если бы мы пошли по пути прямой рекурсии, то сами вызвали бы телефон по поиску на смарт-часах. А косвенная рекурсия предложит нам попросить кого-нибудь набрать номер, чтобы отыскать наконец телефон.
Под разные задачи может использоваться:
- линейная рекурсия — функция для расчетов вызывается один раз;
- каскадная — для расчетов нужны два или больше разных значения от одной функции, поэтому вызывать приходится несколько раз по числу значений.
Рекурсия, если ей не мешать, может работать бесконечно, вызывать себя раз за разом. Такую, правда ни один компьютер нормально обработать не сможет — его электронные мозги закипят.
Поэтому, чтобы мы написали код правильно, получили хорошую оценку, и компьютер не завис после экспериментов, важно задать условие, чтобы рекурсия закончилась. Такое условие называется базовым случаем.
Базовый случай — условие выхода из рекурсии, после которого программа пойдет дальше.
Пока функция не дошла до базового условия, она будет вызывать сама себя и работать внутри каждого прошлого шага. Вот закопается до границы базового случая и начнет выбираться к следующим вычислениям твоего кода.
Глубина рекурсии — количество раз, когда функция вызывает себя.
Благодаря условию, которое прекращает рекурсию, программа не зацикливается.
Отличие рекурсии от цикла
По смыслу цикл и рекурсия очень похожи — что-то надо сделать несколько раз. Вот только цикл просто повторяет алгоритм, который ему напишут, рекурсия возвращается к себе, таков ее путь.
Надо, например, тебе помочь родителям убрать новогоднюю елку. Дело это скучное, не сразу после праздников до этого руки дойдут. Ставишь ты на стол перед собой коробку, куда надо убрать игрушки, открываешь, а там лежит другая коробка.
Если бы твои действия описывались в голове циклом, то ты бы вынул из коробки другую, поставил на стол, загрузил в свободную шары и мишуру, закончил цикл и повторил все команды с новой коробкой, которая осталась на столе.
Если бы мы шли по рекурсии, то вместо того, чтобы вынимать коробку и складывать на свободное место елочные игрушки, новую коробку мы тоже бы открыли. Прямо так, никуда не вынимая. И продолжали бы это делать, пока коробки в коробках не закончились. Когда дойдем до конца и погрузимся на самую глубину рекурсии, будем из нее выбираться — сложим игрушки в самую последнюю открытую коробку, закроем ее и вынем. Будем повторять, пока не переберем все, что было.
Выбирать между рекурсией и циклом нужно в зависимости от задачи.
Циклы — про максимум скорости и минимум нагрузки без переполнения памяти.
Рекурсия — про читаемость, лаконичность и специфичные задачи вроде фракталов и факториалов .
Плюсы и минусы рекурсивных алгоритмов
Какой бы сложной и запутанной не была рекурсия, у нее есть свои преимущества.
Понятно. Код — как тетрадь с конспектами по физике или химии. Чем лучше у отличника почерк, тем проще будет переписать у него новую тему. Рекурсивные коды — это самый понятный почерк среди циклов и функций для других программистов. Не надо вникать в сокращения и особые обозначения, все четко и понятно. Это очень важно, когда код будут смотреть кроме учителя еще куча людей.
Эффективно. Для некоторых задач подойдут только принципы рекурсии — факториалы, числа Фибоначчи, фракталы и древовидные структуры. Когда суть задачи — раз за разом обращаться к себе, то нагляднее и понятнее будет оформить решение точно так же.
Кратко. Запись рекурсивного алгоритма как правило намного короче циклов с теми же задачами. Просто вызываем функцию снова, и не надо прописывать переход к следующему повторению цикла.
Правильно. Рекурсивные алгоритмы не выдадут тебе ошибку вроде «Действия выполнены в неверном порядке». Если в коде что-то не так, зависнет совсем все, и будет понятно, что стало этому причиной.
Все хорошо быть не может, у рекурсии будут и минусы. Если их не учесть, будут большие проблемы.
Бесконечное время работы. При выполнении программы нам очень важно быстро получить ответ на вопрос, потратить минимум времени на поиски информации и вычисления.
Если неправильно написать рекурсивную функцию, она будет вызывать себя, пока может. Мы уже говорили о базовом случае. Если про него забыть или не знать, работать рекурсия будет ооочень долго.
Переполнение памяти. Еще одна особенность рекурсии, которую придется учесть, чтобы программа заработала — это необходимость хранить все данные шагов рекурсии, пока она не дойдет до базового случая. Поэтому глубина рекурсии не может быть бесконечной. Ее ограничивает язык программирования и возможности оперативной памяти твоего компа.
Если надо анализировать много данных, память просто может кончиться. Компьютер скажет, что у него лапки, и дальше не будет считать твой код.
Определение и реализация рекурсии
Повторить алгоритм в программировании можно двумя путями:
- итерационным (циклом);
- рекурсивным.
Чтобы спокойно пользоваться вторым, нужно правильно его задать. Для этого надо прописать два условия:
- рекурсивное, чтобы функция себя вызывала;
- граничное, чтобы она перестала это делать.
Помним о том, что бесконечной памяти у программы нет, и условия должны это учитывать.
Как реализовать рекурсию в Python
Сразу договоримся, что раз выбор написания кода пал на Python, то в нем есть конкретное ограничение для вызовов рекурсии — 1000 раз. Никто не будет мешать тебе попробовать вызвать рекурсию в 1001 раз, только на экране вместо результата вычислений появится ошибка «Переполнение стека».
Посмотрим, зная все нюансы рекурсии, как задать ее на этом языке. Допустим, нам надо написать любимую программистами фразу «Hello, world!» и в каждой новой строке убирать по символу с конца. Можно решить эту задачу циклом, но мы говорим сегодня не о нем.
def greetings(st):
print(st)
if len(st) == 0: # Граничный случай
return
else: # Рекурсивный случай
greetings(st[:-1])
greetings('Hello, world!')
Мы задали границу для рекурсии и условие, при котором она будет себя вызывать. Пока длина строки не станет нулевой, функция будет повторяться.
Как видишь, рекурсию часто задают через конструкцию if, ведь она идеально подходит для описания обоих нужных условий.
Кстати, можно сделать так, что одно условие в функции будет проверять и рекурсивный и граничный:
def greetings(st):
print(st)
if len(st) > 0:
greetings(st[:-1])
greetings('Hello world!')
Мы обращались сегодня к такой математической штуке, как факториал (Произведение всех натуральных чисел от 1 до данного числа. Обозначается восклицательным знаком: 3!=6). Давай посмотрим, как можно описать его на Python через рекурсию:
def fact_recursive(n):
if n == 1: # граничный случай
return 1
else: # рекурсивный случай
return n * fact_recursive(n - 1)
print(fact_recursive(int(input())))
Функция спустится от максимального значения до 1, а потом начнет выходить обратно, постепенно умножая числа. Так она снова придет к максимуму и выдаст ответ на экран.
Проверь себя
Выбери НЕВЕРНОЕ утверждение:
а) рекурсия — функция, алгоритм которой состоит из рекурсивного условия и базового случая;
б) рекурсия — это алгоритм цикла, который повторяет операции определенное количество раз;
в) рекурсия — это поведение функции, при котором она повторяет саму себя.
Глубиной рекурсии называется…
а) количество операций, которые нужно выполнить в алгоритме рекурсии;
б) количество строк кода, которые потребовалось записать для описания рекурсии;
в) количество раз, сколько рекурсивная функция вызывает саму себя.
Что может произойти, если рекурсию задать неправильно?
а) программа выдаст ошибку о неправильном значении;
б) расчеты будут продолжаться бесконечно;
в) программа выдаст неправильный ответ на расчеты.