Как сделать рекурсию

Рекурсия

Зачем функции вызывать саму себя — одна из любимых тем на собеседовании.

Время чтения: больше 15 мин

Открыть/закрыть навигацию по статье

Кратко

Рекурсия в программировании

Повторяющиеся операции
Базовый случай

Факториал с помощью цикла
Факториал с помощью рекурсии

Деревья
Рекурсивный обход

Обновлено 30 сентября 2022

Кратко

Скопировать ссылку «Кратко» Скопировано

Рекурсия — это что-то, что описывает само себя.

Представить рекурсию проще всего на примере зеркального коридора — когда напротив друг друга стоят два зеркала. Если посмотреть в одно, то в нём будет отражение второго, во втором — отражение первого и так далее.

Кадр из фильма «Начало» Нолана

В «Начале» Нолана есть момент с зеркальным коридором, когда в отражении зеркала видно отражение зеркала, в котором видно отражение зеркала, в котором видно.

Второй пример, чуть более академически правильный — это фрактал. Тот же треугольник Серпинского — это пример рекурсии, потому что часть фигуры — это одновременно вся фигура.

Треугольник состоит из 3 точно таких же треугольников

Треугольник состоит из 3 точно таких же треугольников.

Рекурсия в программировании

Скопировать ссылку «Рекурсия в программировании» Скопировано

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

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

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

 // 2^5 = 2 * 2 * 2 * 2 * 2//// 1 шаг: 2// 2 шаг: 2 * 2// 3 шаг: 2 * 2 * 2// 4 шаг: 2 * 2 * 2 * 2// 5 шаг: 2 * 2 * 2 * 2 * 2//// Какой по счёту шаг —// столько и умножений. // 2^5 = 2 * 2 * 2 * 2 * 2 // // 1 шаг: 2 // 2 шаг: 2 * 2 // 3 шаг: 2 * 2 * 2 // 4 шаг: 2 * 2 * 2 * 2 // 5 шаг: 2 * 2 * 2 * 2 * 2 // // Какой по счёту шаг — // столько и умножений.

Но это же можно представить в виде нескольких последовательных умножений на 2:

 // 2^5 = ((((2 * 2) * 2) * 2) * 2)//// 1 шаг: 2// 2 шаг: 2 * 2 (результат 1-го шага * 2)// 3 шаг: 4 * 2 (результат 2-го шага * 2)// 4 шаг: 8 * 2 (результат 3-го шага * 2)// 5 шаг: 16 * 2 (результат 4-го шага * 2)//// Для получения нового результата// мы берём предыдущий и умножаем его на 2. // 2^5 = ((((2 * 2) * 2) * 2) * 2) // // 1 шаг: 2 // 2 шаг: 2 * 2 (результат 1-го шага * 2) // 3 шаг: 4 * 2 (результат 2-го шага * 2) // 4 шаг: 8 * 2 (результат 3-го шага * 2) // 5 шаг: 16 * 2 (результат 4-го шага * 2) // // Для получения нового результата // мы берём предыдущий и умножаем его на 2.

При таком представлении всё возведение в степень — это лишь умножение предыдущего результата на 2:

 // 2^n = 2^(n-1) * 2// Значение степени двойки —// это предыдущее значение, умноженное на 2. // 2^n = 2^(n-1) * 2 // Значение степени двойки — // это предыдущее значение, умноженное на 2.

Именно такие задачи называются рекурсивными — когда часть условия ссылается на всю задачу в целом (или похожую на неё).

У рекурсии 2 составляющие: повторяющиеся операции и базовый случай.

Повторяющиеся операции

Скопировать ссылку «Повторяющиеся операции» Скопировано

В примере с возведением в степень повторяющиеся операции — это умножение.

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

Знаменитая сумма всех натуральных чисел контринтуитивно равняется -1/12. А доказывается это именно рекурсивно.

Базовый случай

Скопировать ссылку «Базовый случай» Скопировано

Вторая важная часть рекурсии — это базовый случай.

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

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

Как только выполнение доходит до базового случая, оно останавливается

Как только выполнение доходит до базового случая, оно останавливается.

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

В JS это приводит к переполнению стека вызовов, и функция останавливается с ошибкой.

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

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

Цикл и рекурсия

Скопировать ссылку «Цикл и рекурсия» Скопировано

Из-за повторяющихся операций рекурсия схожа с циклом. Их часто считают взаимозаменяемыми, но это всё же не совсем так.

Рекурсия проигрывает циклу в следующем:

Отлаживать рекурсию значительно сложнее, чем цикл, а если функция написана плохо — то и просто читать.
Она может приводить к переполнению стека. Особенно это ощутимо в таких языках как JS, где переполнение стека может наступить раньше базового случая с высокой вероятностью.
Её выполнение может (хотя необязательно) занимать больше памяти.

Цикл же проигрывает рекурсии в таких вещах:

Его нельзя использовать в функциональном программировании, потому что он императивен.
Циклом гораздо сложнее обходить вложенные структуры данных, например, каталоги файлов.
Результат выполнения рекурсивной функции проще закэшировать, чтобы ускорить выполнение, с циклом это сделать сложнее.
При работе с общими ресурсами или асинхронными задачами чаще удобнее использовать рекурсивные функции из-за замыканий.

Поэтому на вопрос «Что использовать: рекурсию или цикл?» ответом будет «Зависит от задачи», серебряной пули здесь нет :–)

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

Факториал числа — это произведение всех чисел от единицы до этого числа. Например, факториал 5 — это произведение (1 × 2 × 3 × 4 × 5) = 120.

Факториал с помощью цикла

Скопировать ссылку «Факториал с помощью цикла» Скопировано

Сперва решим задачу нахождения факториала с помощью цикла.

 function factorial(n)  // Начальный результат будет равен 1, // чтобы его можно было умножать на последующие числа. // 0 подходит только для подсчёта суммы, // потому что умножение на 0 всегда даёт 0. let result = 1 for (let i = 0; i < n; i++)  // Так как наш счётчик начинается с 0 // и растёт до n-1, нам нужно прибавить к нему // единицу, чтобы правильно рассчитать произведение. result *= i + 1 > return result> console.log(factorial(5))// 120 function factorial(n)  // Начальный результат будет равен 1, // чтобы его можно было умножать на последующие числа. // 0 подходит только для подсчёта суммы, // потому что умножение на 0 всегда даёт 0. let result = 1 for (let i = 0; i  n; i++)  // Так как наш счётчик начинается с 0 // и растёт до n-1, нам нужно прибавить к нему // единицу, чтобы правильно рассчитать произведение. result *= i + 1 > return result > console.log(factorial(5)) // 120

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

Факториал с помощью рекурсии

Скопировать ссылку «Факториал с помощью рекурсии» Скопировано

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

Хорошим правилом при работе с рекурсией считается первым делом описывать базовый случай (как ранний выход, early return) и только потом — всё остальное. Это позволяет сделать работу с рекурсией безопаснее.

В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции

В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции.

 function factorial(n)  // Если мы пытаемся найти факториал 1, // возвращаем 1 — это базовый случай. if (n <= 1)  return 1 > // В остальных случаях // возвращаем произведение n // на факториал предыдущего числа — // таким образом мы от n дойдём до 1, // перебрав каждое число. return n * factorial(n - 1)> console.log(factorial(5))// 120 function factorial(n)  // Если мы пытаемся найти факториал 1, // возвращаем 1 — это базовый случай. if (n  1)  return 1 > // В остальных случаях // возвращаем произведение n // на факториал предыдущего числа — // таким образом мы от n дойдём до 1, // перебрав каждое число. return n * factorial(n - 1) > console.log(factorial(5)) // 120

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

Процесс вычисления факториала 5 будет состоять из 4 под-вызовов функции

Процесс вычисления факториала 5 будет состоять из 4 под-вызовов функции factorial ( ) .

Разберём по шагам, что происходит с переменной n и результатом функции factorial после каждого вызова:

 /* Сперва мы «спускаемся вглубь» вызовов.Первый вызов создаёт новую область видимости:factorial(5)  в ней переменная n становится равной 5; n - 1 => 4; функция возвращает 5 * factorial(4); Второй вызов создаёт ещё одну область видимости: factorial(4)  n => 4 n - 1 => 3 return 4 * factorial(3) Третий вызов, ещё одна область видимости: factorial(3)  n => 3 n - 1 => 2 return 3 * factorial(2) Четвёртый вызов, ещё одна область: factorial(2)  n => 2 n - 1 => 1 return 2 * factorial(1) Финальный вызов, последняя область, базовый случай: factorial(1)  n => 1 Так как это базовый случай, возвращаем 1. После базового случая мы «поднимаемся наверх». > В этот момент результат factorial(1) становится равен 1 Возвращаем return 2 * 1 > Результат factorial(2) => 2 return 3 * 2 > factorial(3) => 6 return 4 * 6 > factorial(4) => 24 return 5 * 24> После каждого return область видимости соответствующей функции очищается.Результат вызова становится равным конкретному числу. */ /* Сперва мы «спускаемся вглубь» вызовов. Первый вызов создаёт новую область видимости: factorial(5) < в ней переменная n становится равной 5; n - 1 =>4; функция возвращает 5 * factorial(4); Второй вызов создаёт ещё одну область видимости: factorial(4) < n =>4 n - 1 => 3 return 4 * factorial(3) Третий вызов, ещё одна область видимости: factorial(3) < n =>3 n - 1 => 2 return 3 * factorial(2) Четвёртый вызов, ещё одна область: factorial(2) < n =>2 n - 1 => 1 return 2 * factorial(1) Финальный вызов, последняя область, базовый случай: factorial(1) < n =>1 Так как это базовый случай, возвращаем 1. После базового случая мы «поднимаемся наверх». > В этот момент результат factorial(1) становится равен 1 Возвращаем return 2 * 1 > Результат factorial(2) => 2 return 3 * 2 > factorial(3) => 6 return 4 * 6 > factorial(4) => 24 return 5 * 24 > После каждого return область видимости соответствующей функции очищается. Результат вызова становится равным конкретному числу. */

Минусы такой реализации:

Много областей видимости (замыканий), которые относительно требовательны к памяти.
Относительно просто читать, но сложнее отлаживать, чем цикл.

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

Рекурсивные структуры данных

Скопировать ссылку «Рекурсивные структуры данных» Скопировано

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

Структура данных — это контейнер, который хранит данные в определённом формате. Этот контейнер решает, каким образом внешний мир может эти данные считать или изменить.

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

Деревья

Скопировать ссылку «Деревья» Скопировано

Дерево — это структура, в которой у каждого узла может быть несколько дочерних подузлов — «детей».

Мы уже встречались с деревьями в статье «Как браузер рисует страницы». Мы рассматривали DOM, CSSOM и Render Tree. Вспомним, как выглядит DOM-дерево.

      Hello   Hello world      html ______|_______ | | body head ___|____ ___|___ | | | | p img meta title | | "Hello world" "Hello" -->  html> head> meta charset="utf-8"> title>Hellotitle> head> body> p class="text">Hello worldp> img src="/hello.jpg" alt="Привет!"> body> html>


У каждого дерева есть корень — узел, из которого берут начало остальные узлы. Корень DOM-дерева выше — это элемент html .
Работать с деревьями с помощью циклов (итеративно) неудобно. Представьте, что мы хотим получить названия всех элементов на странице. Да, мы можем пройтись циклом по 1-му уровню или 2-му, но дальше нужно думать, как определять, где мы были, где ещё нет и куда идти дальше.






С рекурсией обход дерева становится немного проще.
Рекурсивный обход
Скопировать ссылку "Рекурсивный обход" Скопировано
В случае с рекурсией мы можем придумать например такой алгоритм для обхода дерева:

базовый случай: если у узла дерева нет дочерних узлов вовсе, или мы обошли их все — возвращаем название этого элемента;
повторяемые операции: рекурсивно обходим каждый дочерний элемент, собирая их названия.

 // Псевдокод: function nameOf(element)  /* . Возвращает название элемента. */> function eachChild(element, func)  /* . Вызывает функцию func на каждом дочернем узле элемента element. */> function childrenOf(node)  /* . Возвращает дочерние узлы данного узла, если их нет, возвращает null. */> function traverse(treeNode)  // Если дочерних узлов нет, это базовый случай; // возвращаем массив с названием текущего элемента. // Массив здесь нужен для последовательности, // так как дальше мы будем возвращать массивы с названиями других узлов, // то чтобы нам не приходилось каждый раз проверять тип результата, // мы всегда возвращаем массив. if (!childrenOf(treeNode))  return [nameOf(treeNode)] > // Если же случай не базовый, // то мы проходим по каждому из дочерних узлов // и вызываем на нём функцию traverse. // В nameArrays у нас получится список списков названий. // (На каждый дочерний узел по списку.) const namesArrays = eachChild(treeNode, traverse) // Нам останется сделать список плоским // и вернуть его как результат. const names = namesArrays.flat() return names> // Начав обход с корневого узла дерева,// вы получим на выходе список имён всех элементов.const names = traverse(rootNode) // Псевдокод: function nameOf(element)  /* . Возвращает название элемента. */ > function eachChild(element, func)  /* . Вызывает функцию func на каждом дочернем узле элемента element. */ > function childrenOf(node)  /* . Возвращает дочерние узлы данного узла, если их нет, возвращает null. */ > function traverse(treeNode)  // Если дочерних узлов нет, это базовый случай; // возвращаем массив с названием текущего элемента. // Массив здесь нужен для последовательности, // так как дальше мы будем возвращать массивы с названиями других узлов, // то чтобы нам не приходилось каждый раз проверять тип результата, // мы всегда возвращаем массив. if (!childrenOf(treeNode))  return [nameOf(treeNode)] > // Если же случай не базовый, // то мы проходим по каждому из дочерних узлов // и вызываем на нём функцию traverse. // В nameArrays у нас получится список списков названий. // (На каждый дочерний узел по списку.) const namesArrays = eachChild(treeNode, traverse) // Нам останется сделать список плоским // и вернуть его как результат. const names = namesArrays.flat() return names > // Начав обход с корневого узла дерева, // вы получим на выходе список имён всех элементов. const names = traverse(rootNode)      
Когда использовать рекурсию
Скопировать ссылку "Когда использовать рекурсию" Скопировано
Сама по себе рекурсия — это всего лишь инструмент. Нет чётких правил, когда её надо использовать, а когда — нет. Есть лишь некоторые рекомендации.

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

Когда использовать цикл
Скопировать ссылку "Когда использовать цикл" Скопировано

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

Рекурсия
Рекурсия (recursion) — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга.
Известная шутка гласит: «Чтобы понять рекурсию, надо понять рекурсию».







«IT-специалист с нуля» наш лучший курс для старта в IT
Рекурсия считается одним из основных понятий в информатике. Это метод решения задач, похожий на математическую индукцию: чтобы функция выполнилась, нужно сначала получить ее результат при вызове с другим значением.
Это работает так: функция A от единицы запускает функцию A от двойки, та — от тройки, и так далее, пока не будет высчитано нужное значение. Чтобы рекурсивный вызов закончился, нужно сразу прописать в функции A условие выхода из рекурсии: например, если получено какое-то значение, нужно не запускать функцию заново, а вернуть некоторый результат.
Если не прописать условие выхода, рекурсия будет бесконечной. А пока условие выхода не достигнуто, все вызванные экземпляры функции A будут работать одновременно — один вкладывает другой в себя.
Поддержка рекурсивного вызова есть практически во всех современных языках программирования.
Профессия / 8 месяцев

IT-специалист с нуля
Попробуйте 9 профессий за 2 месяца и выберите подходящую вам







Кто пользуется рекурсией и зачем она нужна
Рекурсия время от времени нужна программистам, чтобы решать различные задачи. Есть задания, которые проще и интуитивно понятнее решаются с ее помощью, а есть те, для которых есть более оптимальные алгоритмы.
Обычно рекурсию применяют при расчетах, которые подразумевают использование результата одного шага для подсчитывания другого. Например, расчет фрактала и его рисование. Зачастую подобные задачи можно решить и без рекурсии, но ее использование делает код проще, короче и быстрее, чем альтернативные варианты. Правда, рекурсия может слишком нагружать компьютер, поэтому такие решения применяют не всегда.
Рекурсию можно встретить и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Например, фрактальные формы вроде листа папоротника или снежинки — рекурсивные. Вложенные предложения — тоже. А самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.
Программисты пользуются рекурсией и ради забавы. Например, известная аббревиатура GNU расшифровывается как GNU is Not Unix – первая буква скрывает под собой ту же аббревиатуру. Это тоже рекурсия.
Отличия рекурсии от цикла
На интуитивном уровне рекурсивный вызов легко перепутать с циклом. И то, и другое понятие подразумевает, что функция выполняется несколько раз. Но есть принципиальное различие:

в цикле новые функции не вызываются внутри вызванных ранее;
рекурсия же — это функция, вызывающая сама себя с другими аргументами.

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






Прерывание рекурсии
Если рекурсивной функции не задать условия для выхода, она будет работать бесконечно, пока огромное количество ее экземпляров не «съест» всю оперативную память устройства и не переполнит стек вызовов. Поэтому разработчик должен предусмотреть пути выхода из рекурсивного процесса.
Обычно путь выхода — это какое-то условие, которое проверяется в самом начале выполнения функции. Если оно выполняется, функция вызовет себя снова, если нет — выдаст какое-то значение, отдаст его предыдущему «соседу» и закроется.
Например, если n > 1, то вызвать A(n-1). Иначе вернуть 1. Получается, что когда n станет меньше или равен единице, то A не запустится заново — очередной экземпляр просто вернет единицу. Остальные экземпляры получат нужный себе результат и тоже закроются по каскаду. Этот процесс называется обратным ходом рекурсии. А то, что было до него, — прямым ходом.
Количество открытых в итоге функций называется глубиной рекурсии.
Пример рекурсии: расчет чисел Фибоначчи
Известный пример рекурсивных расчетов — числа Фибоначчи. Каждое следующее число в ряду — сумма двух предыдущих, начиная с 1.
Получается так: 1, 1, 2, 3, 5, 8, 13, 21 и так далее. Использование рекурсии здесь — напрашивающийся и интуитивно понятный способ расчета:

допустим, функция называется fibonacci(n) и рассчитывает n-е по счету число Фибоначчи;
на первом шаге функция вызывает fibonacci(n-1) и fibonacci(n-2), то есть себя, но с другими аргументами, и складывает получившиеся результаты;
новые вызовы будут делать то же самое, пока n не дойдет до единицы или нуля — это первое число Фибоначчи, и в таком случае функция вернет 1;
предыдущий экземпляр функции получит два результата 1 — от единицы и нуля, сложит их и отправит «назад» к более ранним соседям;
в итоге все вызванные функции получат от своих «потомков» ответ, сложат полученные значения и вернут их самой первой функции fibonacci(n);
та сложит финальные значения, вернет результат и закроется.

Это только один простой пример; рекурсивных алгоритмов намного больше. Еще один известный — расчет факториала числа.






Курс для новичков «IT-специалист 
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить
Другие примеры рекурсивных расчетов

Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
Расчет и изображение фракталов — конструкций, где более мелкие элементы повторяют более крупные. Яркие примеры фракталов — снежинка и лист папоротника.
Обход ветвящихся структур данных, например графов и деревьев.
Компьютерный анализ естественного языка, фраз и предложений.
Поиск пути в лабиринте и построение маршрутов — к примеру, алгоритмы DFS и BFS.
Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
Операции с системами счисления, к примеру перевод чисел из одной в другую.

За пределами математики и информатики можно вспомнить много других примеров рекурсии: от самовозбуждения электронных схем до сказок «Тысячи и одной ночи».
Прямая и косвенная рекурсия
Рекурсию можно условно разделить на прямую и косвенную.

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

Еще бывают линейная и каскадная рекурсии. В линейной экземпляр функции вызывает сам себя только один раз, в каскадной — несколько. Например, расчет чисел Фибоначчи — каскадная рекурсия, потому что функция вызывает себя дважды: для n-1 и n-2.
Рекурсивный и итеративный процессы
Одну и ту же рекурсию можно использовать по-разному. Например, есть понятия рекурсивного и итеративного процесса. И там, и там применяется рекурсия, но различается подход к ней.
В рекурсивном процессе все расчеты откладываются «на потом», как в примере с числами Фибоначчи. Конечный расчет делает тот экземпляр функции, который вызвали в последнюю очередь, а потом результаты по каскаду передаются предыдущим.
В итеративном процессе все наоборот. Функция считает всё, что может посчитать, и только потом вызывает свой новый экземпляр и передает наработки ему.
Частный случай рекурсии — хвостовая: в ней вызов самой себя — последнее, что делает функция, перед тем как завершиться.






Преимущества рекурсии
Рекурсивный подход многим нравится, потому что он изящный и емкий, а описать такой алгоритм часто быстрее, чем аналоги. Вот основные преимущества создания рекуррентных решений.
Ясность. Прочитать рекурсивный код обычно проще, чем программу, полную ухищрений для решения той же задачи без рекурсии. Это важный плюс, если речь идет о коммерческом программировании, где код часто смотрят другие люди.
Наглядность. Некоторые задачи, вроде тех же чисел Фибоначчи или факториалов, — рекурсивные по самому своему определению. То же самое касается задач на ряды, фракталы и так далее. Решить такую задачу через рекурсию — один из наиболее наглядных и интуитивно понятных способов. Более того: люди пользуются рекурсией все время, даже просто когда разговаривают, и это лишний раз работает на интуитивное ее понимание.
Краткость. Рекурсивная функция обычно короче, чем реализация без рекурсии. Разработчику проще и удобнее написать несколько строк кода, чем создавать огромную программу, тратить время и силы и путаться в написанном.
Красота. Наконец, сам концепт многие считают красивым и изящным. Это и правда так — посмотрите на фракталы и снежинки: в них есть определенная красота. Рекурсию используют даже в искусстве: от матрешек до сложных узоров, украшающих готические соборы.
Недостатки рекурсии
Недостатков у рекурсивного подхода два, но они критичные и серьезно ограничивают применение этой концепции даже там, где она напрашивается.
Риск переполнения. При всем перечисленном программисты пользуются рекурсией довольно осторожно. Она устроена так, что, пока не выполнится последний вызов функции, все предыдущие не завершатся — ведь они как бы «вкладывают» в себя последующие. Поэтому такие программы отнимают много ресурсов компьютера. Так что разработчики смотрят и на параметр производительности и решают, что выгоднее в конкретном случае — использовать рекурсию или нет.
Риск бесконечности. Если что-то пошло не так и программист случайно получил бесконечную рекурсию, единственный выход — принудительно закрыть программу. А потом переписать ее, чтобы ошибка не повторялась при следующем запуске.






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

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

Понимание, что лучше использовать в конкретном случае, приходит с опытом. Начинающим разработчикам в любом случае стоит освоить рекурсию: это важная часть программирования и информатики вообще.
Как начать работать с рекурсией
Концепт и примеры рекурсивных функций можно найти в любом учебнике по программированию. Обычно начинающим предлагают потренироваться на простых «классических» задачах вроде чисел Фибоначчи или расчета факториала. Затем можно переходить к более сложным заданиям: обход графа, анализ текста или что-либо еще. А какой язык выбрать — зависит от ваших предпочтений и пожеланий к отрасли.
Если вы хотите познакомиться с большим количеством концептов из информатики — записывайтесь на курсы! Вы узнаете, как работают разные процессы, и сделаете первые шаги к новой востребованной профессии.
IT-специалист с нуля
Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.
Рекурсия
Чтобы понять рекурсию нужно понять рекурсию.
Рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A.







Программа разрабатывается сведением исходной задачи к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме.
Например, для вычисления F(N) может понадобиться вычислить F(N−1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Итак, функция является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие функции). Заметим, что при косвенном обращении все функции в цепочке – рекурсивные.
Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что \(0!=1\), \(1!=1\). А как вычислить величину \(n!\) для бОльших \(n\)? Если бы мы могли вычислить величину \((n−1)!\), то тогда мы легко вычислили бы \(n!\), поскольку \(n!=n\cdot(n−1)!\). Но как вычислить \((n−1)!\)? Если бы мы вычислили \((n−2)!\), то мы сможем вычисли и \((n−1)! = (n−1)\cdot(n−2)!\). А как вычислить \((n−2)!\)? Если бы. В конце концов, мы дойдем до величины \(0!\), которая равна \(1\). Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Си:
int factorial(int n)
 if (n == 0) 
return 1; 
else 
return factorial(n - 1) * n;
>
Краткая формулировка обоснования рекурсивного алгоритма вычисления факториала:






если N = 0, то N! = 1
Как это работает?
Допустим, мы вызвали функцию factorial(4). Будет вызвана функция, у которой значение параметра n равно 4. Она проверит условие n == 0, поскольку условие ложно, то будет выполнена инструкция return n * factorial(n - 1). Но чтобы вычислить это значение, будет вызвана функция factorial(3), так как параметр n имеет значение, равное 4. Теперь в памяти будет находиться две функции factorial -- одна со значением параметра n равным 4, а другая — со значением 3. При этом активна будет последняя функция.
Эта функция в свою очередь вызовет функцию factorial(2), та вызовет функцию factorial(1), затем factorial(0). В случае этой функции ничего более вызвано не будет, функция просто вернет значение 1, и управление вернется в функцию factorial(1). Та умножит значение n = 1 на значение 1, которое вернула функция factorial(0), и вернет полученное произведение, равное 1. Управление вернется в функцию factorial(2), которая умножит n = 2 на значение 1, которое вернула функция factorial(1) и вернет полученное произведение, равное 2. Функция factorial(3) вернет \(3\times2 = 6\), а функция factorial(4) вернет \(4 \times 6 == 24\).
Таблица последовательности вызовов функции приведена ниже. Значения функции возвращают в порядке, обратном порядку их вызова, то есть сначала заканчивает работу функция factorial(0), затем factorial(1) и т. д.



С какими параметрами вызвана функция
Какое значение вернула


factorial(4)
4 * 6 = 24


factorial(3)
3 * 2 = 6


factorial(2)
2 * 1 = 2


factorial(1)
1 * 1 = 1


factorial(0)
1



При отладке программы всю последовательность вложенных вызовов рекуррентных функций можно изучить в окне «Call Stack» («стек вызовов») в режиме отладки.
Для каждой вызываемой функции значения локальных переменных будут своими.
Для того, чтобы реализовать рекурсию нужно ответить на следующие вопросы:

Какой случай (для какого набора параметров) будет крайним (простым) и что функция возвращает в этом случае?
Как свести задачу для какого-то набора параметров (за исключением крайнего случая) к задаче, для другого набора параметров (как правило, с меньшими значениями)?

При этом программирование рекурсии выглядит так. Функция должна сначала проверить, не является ли переданный набор параметров простым (крайним) случаем. В этом случае функция должна вернуть значение (или выполнить действия), соответствующие простому случаю. Иначе функция должна вызвать себя рекурсивно для другого набора параметров, и на основе полученных значений вычислить значение, которое она должна вернуть.
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Рекурсия изнутри
Это может показаться удивительным, но самовызов функции/процедуры ничем не отличается от вызова другой функции/процедуры. Что происходит, если одна функция вызывает другую? В общих чертах следующее:

в памяти размещаются параметры, передаваемые функции (но не параметры-переменные, т. к. они передаются по ссылке!);
для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);
запоминается адрес возврата в вызывающую функцию;
управление передается вызванной функции.

Если функцию или процедуру вызвать повторно из другой функции/процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.
Простыми словами о рекурсии
В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.
Рекурсию также можно сравнить с матрёшкой. Первая кукла самая большая, за ней идёт точно такая же кукла, но поменьше. Суть матрёшки состоит в том, что вы можете открывать её и доставать из неё точно такую же куклу, только немного меньше. Такой продолжительный процесс длится до тех пор, пока вы не дойдёте до последней куклы, которая и прервёт цикл. Так выглядит визуальная репрезентация рекурсии.
Не приведёт ли рекурсивная функция к бесконечному циклу?
Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.
Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:
function countDown(n)console.log(n)if(n > 1) countDown(n -1) // вызов рекурсии
> else return true // основное действие 
>
>
countDown(5)// 5
// 4
// 3
// 2
// 1
countDown(-1)
// - 1 // true
Как прервать рекурсию:
Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:
Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .
По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.
Проще говоря, рекурсия делает то же, что и код ниже:
countDown(5) 
countDown(4) 
countDown(3) 
countDown(2) 
countDown(1) 
return 
return 
return 
return
return
Плюсы и минусы рекурсивных функций
Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.
Плюсы:

Рекурсивный код снижает время выполнения функции.

Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.
В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия
И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.
Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.
Минусы:

Рекурсивные функции занимают много места.

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

Рекурсивные функции замедляют программу.

Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.
Что такое «стек»?
Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.
Стеки замечательны тем, что они очень быстрые. Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции pop() , push() и empty() .
Стоит ли использовать рекурсии вместо обычных циклов?
Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.

Как освоить алгоритмы?
Алгоритмы машинного обучения простым языком. Часть 1
4 принципа успешной поисковой системы и не только



Похожие публикации:

Github actions что это
Как настроить страницу 404
Как обойти чебурнет
Как установить npm в vs code

Как сделать рекурсию

Рекурсия

Кратко

Рекурсия в программировании

Повторяющиеся операции

Базовый случай

Цикл и рекурсия

Факториал с помощью цикла

Факториал с помощью рекурсии

Рекурсивные структуры данных

Деревья

Рекурсивный обход

Когда использовать рекурсию

Когда использовать цикл

Рекурсия

Кто пользуется рекурсией и зачем она нужна

Отличия рекурсии от цикла

Прерывание рекурсии

Пример рекурсии: расчет чисел Фибоначчи

Другие примеры рекурсивных расчетов

Прямая и косвенная рекурсия

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

Преимущества рекурсии

Недостатки рекурсии

Чем пользоваться: рекурсией или циклом

Как начать работать с рекурсией

Рекурсия

Рекурсия изнутри

Простыми словами о рекурсии

Не приведёт ли рекурсивная функция к бесконечному циклу?

Как прервать рекурсию:

Плюсы и минусы рекурсивных функций

Плюсы:

Минусы:

Что такое «стек»?

Стоит ли использовать рекурсии вместо обычных циклов?

Добавить комментарий Отменить ответ