Рекурсия – одно из основных понятий программирования, хотя одним только программированием она не ограничивается.
Понимание рекурсии кому-то кажется сложным, но я считаю, это не совсем так. На обычном, бытовом уровне рекурсия как раз должна быть понятна. Курс - это курс, ре - это повторение, рекурсия - повторение курса.
Рекурсивным является любое высказывание или объект или логическая концепция, которые для своего полного описания должны повторить сами себя, что делает полное описание невозможным.
Например: У попа была собака...
Или: Дерево – это ствол, из которого растут ветки. Ствол – это палка. Ветка – это дерево.
Чтобы написать определение дерева, использовано определение дерева. Это определение дерева содержит в себе определение дерева и таким образом никогда не закончится. Каждый раз, когда мы попадаем на определение дерева, мы как бы ныряем вглубь него, но выхода на поверхность никогда не будет (как и у попа с собакой).
Даже если это непривычно осознавать или представлять, общее понимание должно быть правильное. Проблемы, однако, начинаются, когда с рекурсией сталкиваются именно в программировании.
Сложности реализации рекурсии в программном коде, несмотря на её видимую простоту, заставляют вскипать мозги у новичков и не только. Давайте попробуем немножко всё это разрулить.
Что такое рекурсия в программировании?
Классический пример – это функция, которая вызывает сама себя. У функции есть имя и определение, то есть код, который находится внутри неё. Если в этом коде мы вызываем функцию с тем же именем, значит для завершения её определения нужно обратиться к ней самой. И как только мы её вызовем, она вызовет себя ещё раз и ещё и т.д.
Самый простой пример (не делайте так)
Это бесконечная последовательность вызовов функции test(), которая внутри себя вызывает сама себя и никогда не вернётся.
А цикл не рекурсия?
Нет. Хотя мы и можем устроить бесконечный цикл с вызовом функции:
И вроде бы это будет то же самое, но цикл – не рекурсия. Это просто повторение.
Посмотрите внимательно: цикл бесконечное количество раз повторяет функцию test(), но сама функция не рекурсивна: она вызывается, что-то делает и заканчивается. Из неё есть возврат. И значит, все повторения случаются на верхнем слое состояния программы, не уходя вглубь.
Уход вглубь происходит только в момент вызова функции, но при возврате из функции мы снова "всплываем".
Конкретно уход вглубь и является основным свойством рекурсии – из неё нельзя вернуться, можно только заходить всё глубже и глубже.
Но как понять "вглубь", если, скажем, память компьютера линейна и никакой глубины в ней нет?
Это лишь метафора. Уход вглубь означает, что мы покидаем то состояние, в котором находились, и попадаем в новое состояние. Само состояние в программе представлено просто неким набором переменных, и вот этот самый набор мы покидаем. Но он не теряется, так как при "всплытии" мы получаем его обратно. Все состояния, которые мы покинули, продолжают существовать, вложенные друг в друга как матрёшки. Как это происходит, сейчас разберём.
В учебниках для примера рекурсии обычно используют задачу вычисления факториала числа N. Это 1*2*3*...*N. Так как в этой последовательности любое число N умножается на умножение всех чисел меньше N, факториал можно легко записать в рекурсивном виде:
Факториал(N) = N * Факториал(N-1)
Обратите внимание, что в функции делается проверка: если n равно 1 или 2, то функция сразу возвращает это значение. Его не нужно рекурсивно вычислять, оно уже вычислено. То есть,
Факториал(1) = 1
Факториал(2) = 1*2 = 2
Наличие такого условия в функции делает рекурсию конечной. То есть возврат всё-таки когда-нибудь произойдёт. Иначе в такой функции не было бы никакого смысла – программа бы просто обрушилась и всё.
Давайте разберём, как будет происходить вычисление факториала от 5. Мы вызываем функцию factorial() и передаём ей параметр 5:
factorial(5)
Внутри функции этот параметр называется n. Функция видит: n > 2, значит она вычисляет факториал так:
n * factorial(n - 1)
или, по факту:
5 * factorial(4)
Как только мы добрались до factorial(4), прямо в этом месте происходит новый вызов функции и погружение на уровень ниже.
Напрягите мозг: код функции нужно начать читать с начала. Мы смотрим на тот же код той же самой функции, но это уже функция в другом состоянии.
Для неё параметр n уже другой. Мы покинули состояние, где n = 5, и теперь имеем состояние, где n = 4. В свою очередь, это состояние вычислит факториал:
4 * factorial(3)
И мы уйдём ещё глубже, покинув состояние, где n = 4, и попав в состояние, где n = 3. Так мы дойдём до состояния, где n = 2.
Увидев, что n = 2, функция вернёт это значение. Произойдёт "всплытие" на уровень выше. А что у нас там на уровне выше? А там состояние, где n = 3, которое мы покинули и теперь в него вернулись. Возвращаясь в него, мы не читаем код функции с начала, а продолжаем ровно с того места, откуда ушли.
Значит, в этом состоянии мы уже получили результат 3 * factorial(2), то есть 6, и возвращаем его наверх. А наверху опять предыдущее состояние, где n = 4, и вот мы в него тоже вернулись и завершили вычисление 4 * 6 = 24, и возвращаем этот результат наверх. В конце концов мы вернёмся в самое верхнее состояние, где n = 5, и сможем вернуть финальный результат, окончально выйдя из рекурсии.
Как сохраняются состояния, которые мы покинули?
И как нам удаётся в них вернуться и продолжить работу? Ранее я писал, что для вызова функций используется стек:
Именно в стеке сохраняется адрес, куда нужно вернуться. Каждый раз, когда мы вызываем функцию, текущий адрес выполнения программы кладется в стек, а когда возвращаемся из функции, он забирается из стека. Если внутри функции вызвать снова функцию и внутри неё снова функцию, то текущие адреса будут складываться в стек "стопкой", а при возврате так же разбираться из стопки.
Но как быть с состояниями?
Каждая функция, вызванная рекурсивно, имеет своё состояние параметра n. И опять же, параметры, передаваемые в функцию, сохраняются в стек. То есть при возврате из функции в функцию восстанавливается не только текуший адрес выполнения, но и текущие параметры.
Поэтому глядя на код рекурсивной функции, мы должны представлять её во всех состояниях одновременно. В этом и состоит главная сложность. Функция вычисления факториала максимально проста, то есть проще уже никак. Но рекурсивные функции могут быть более сложными и запутанными (например, обход дерева или построение пути в графе), и вот там реально можно запутаться самим.
Но – побольше практики, побольше решённых самостоятельно задач, и всё будет хорошо.
Нужно ли вычислять факториал рекурсивно?
Нет, это задача только для знакомства с рекурсией. Более просто и эффективно факториал можно вычислить с помощью обычного цикла.
Бывает ли рекурсия без функции в функции?
Помните, что каждый вызов функции – это нагрузка на стек, а он не резиновый. Поэтому многие рекурсивные задачи просто нельзя писать, используя вызов функции из функции. Вы рискуете получить переполнение стека.
Любую рекурсию можно сделать без вызова функции из функции. Например, через обычный цикл. Но ведь цикл не рекурсия? Да, но только потому что в нём нет сохранения и восстановления состояний. При вызове функций это происходит автоматически. Если же вы самостоятельно напишете код для поддержки состояний, то с его помощью можете организовать рекурсию как угодно. Отличие этого кода будет в том, что хранить состояния он будет не в стеке, а в специально выделенной области памяти (массиве), которая не создаст риска переполнения стека.