Что такое рекурсия и рекурсивный метод?

Понятие рекурсии не является специализированным для компьютерных наук и имеет естественную природу.

Рекурсией называется ситуация, когда некоторый объект содержит в своём описании самого себя, то есть является своей частью. Если кратко, рекурсия позволяет уходить от простейших императивно написанных итераций к более декларативному стилю написания кода.

Примеры рекурсии

Живым примером рекурсии является рост дерева – из ствола дерева растут более маленькие деревья – ветки, из них ещё ветки, и так далее, пока не останутся только листья. Рекурсия в природе может быть бесконечна – если дерево не умрёт, из веток будут продолжать расти новые ветки, из них – новые, и так без остановки.

Рекурсия также часто встречается как художественный приём - наверняка многие из вас видели, как художник, который рисует картину, на которой изображён художник, который рисует художника, и так далее.

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

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

Существует два основных процесса, в которых может быть использована рекурсия. Такие процессы называются рекурсивным и итеративным.

Что такое рекурсивный процесс?

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

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

Пример

Предположим, мы хотим вычислить факториал числа 5. Факториал вычисляется для всех неотрицательных чисел. Таким образом, мы будем последовательно раскрывать по одному множителю до тех пор, пока не достигнем условия выхода из рекурсивного цикла. Условием выхода из рекурсивного цикла в данном случае будет достижение последним множителем, являющимся факториалом, значения ноль, то есть операция вычисления факториала для ноля будет последней для рекурсии. Это будет выглядеть следующим образом:

5! = 5 × 4! =>
5 × 4 × 3! =>
5 × 4 × 3 × 2! =>
5 × 4 × 3 × 2 × 1! =>
5 × 4 × 3 × 2 × 1 × 0! =>
5 × 4 × 3 × 2 × 1 × 1

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

Воспроизведём вышеназванный пример в коде для понимания реализации рекурсивной функции:

С рекурсивным понятно, а что касаемо итеративного процесса?

Теперь разберём итеративный процесс. Как уже упоминалось, его особенностью является то, что мы не дожидаемся полного «раскручивания» цепочки вызовов для выполнения действий над аргументами функций, а выполняем любые вычисления в каждой итерации, сохраняя их, используя аккумулятор.

Посмотрим, как это происходит уже на известном нам примере с факториалом:

5! = 5 × 4! => // На этом шаге у нас появляется аккумулятор, равный 5
20 × 3! => // Вычисляем промежуточный результат, который равен 20
60 × 2! => // Продолжаем пересчитывать промежуточный результат...
120 × 1! => // Продолжаем пересчитывать промежуточный результат...
120 × 0! => // Продолжаем пересчитывать промежуточный результат...
120 // Терминальное условие достигнуто, останавливаемся.

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

Пример

В коде этот подход реализовать более трудоёмко, давай посмотрим на пример:

Итого

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

P.S. Если эта статья была для тебя полезной, ставь ❤ и делись ей со своими друзьями! 😊