Функция которая вызывает сама себя

Что такое рекурсия, рекурсивный и итеративный процесс в программировании

Рекурсия vs рекурсивный или итеративный процесс: в чем разница

Рекурсия — это функция, которая вызывает саму себя, но с другими значениями параметров.

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

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

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

Бесплатные курсы по программированию в Хекслете

• Освойте азы современных языков программирования
• Изучите работу с Git и командной строкой
• Выберите себе профессию или улучшите навыки

Методы решения задач с помощью рекурсии

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

Давайте продолжим аналогию с музыкальной гармонией и подумаем про фортепиано. При написании музыки используем эту концепцию — «гармонию звуков». Можно придумать разные способы: рассчитывать частоты звуков — ноты — математическими формулами или рассчитывать правильные расстояния между клавишами.

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

В чем отличие рекурсивного процесса от итеративного

Рекурсивный процесс на каждом шаге рекурсии говорит «я это запомню и потом посчитаю». «Потом» наступает в самом конце.

• Если рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел, чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя
• Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа

На этой картинке видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел

Рекурсивный процесс — это процесс с отложенным вычислением.

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

• Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов
• Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать

А на этой картинке видно, что использование памяти не растет.

Подытожим в шуточной форме. Рекурсивный процесс — это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится.

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

Что такое рекурсивные функции и в чем особенность их применения

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

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

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

Читайте также: Как проверить качество кода: функциональное и нефункциональное тестирование

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

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

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

Что такое хвостовая рекурсия

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

Для этого служит так называемая оптимизация хвостовой рекурсии (Tail call optimization). Итеративный процесс, который мы рассмотрели, как раз можно отнести к хвостовой рекурсии. Благодаря оптимизации состояния стека, она придает итеративному процессу вид «плоской» итерации. Так исключается его переполнение из-за большой глубины рекурсии.

Хвостовая рекурсия и ее оптимизация широко используется при написании программ на функциональных языках программирования.

Бесплатные курсы по программированию в Хекслете

• Освойте азы современных языков программирования
• Изучите работу с Git и командной строкой
• Выберите себе профессию или улучшите навыки

Рекурсия — Python: Функции

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

Что такое рекурсия

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

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

def factorial(n): if n  0: return 1 return n * factorial(n - 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py

Эта функция вычисляет факториал числа n через умножение числа на факториал числа n — 1 .

Условие завершения рекурсии

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

В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:

• По рекурсивной — в этой ветке произойдет вызов себя
• По терминальной — закончит вычисление и вернет результат

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

• Уменьшение счетчика
• Отбрасывание головы списка при движении к его хвосту
• Вызов себя для части исходной структуры при обработке древовидных структур данных

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

Переполнение стека

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

Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.

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

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

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

Так выглядит переполнение стека при подсчете факториала:

factorial(1000) # Traceback (most recent call last): # File "", line 1, in # File "", line 4, in factorial # File "", line 4, in factorial # File "", line 4, in factorial # [Previous line repeated 995 more times] # File "", line 2, in factorial # RecursionError: maximum recursion depth exceeded in comparison 

Сообщение говорит, что превышена максимальная глубина рекурсии. Глубиной рекурсии называется количество последовательных вызовов себя без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.

Зачем нужна рекурсия

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

Виды рекурсии

Рекурсии можно разделить на два вида по тому, как они себя вызывают:

• Прямая — когда функция вызывает себя
• Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую

Так же рекурсии можно разделить по количеству рекурсивных вызовов:

• Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с factorial . Уточним, что «один раз» — это не про общее количество вызовов функции в теле. Речь идет о количестве вызовов, результаты которых нужны для одного общего вычисления
• Каскадная — когда функция вызывает себя несколько раз

Рассмотрим подробнее линейную и каскадную рекурсию.

Пример линейной рекурсии

Если рекурсия в функции проверяет Гипотезу Коллатца , она считается линейной:

def collatz(n): if n == 1: return True if n % 2 == 0: return collatz(n // 2) return collatz(n * 3 + 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py

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

Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:

• Начало (голову)
• Остальную часть коллекции (хвост)

Дальше хвост также можно разложить на голову и новый хвост. И так до тех пор, пока не останется голова и пустой хвост:

 [1, [2, 3]] -> [1, [2, [3]]] -> [1, [2, [3, []]]] 

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

# Функция рекурсивно обходит список, суммируя числа из него def sum(array): # Мы можем использовать оператор упаковки для записи в хвост остальной части списка head, *tail = array if not tail: return head return head + sum(tail) 

Пример каскадной рекурсии

Если рекурсия в функции вычисляет очередное Число Фибоначчи , она называется каскадной:

def fibonacci(n): if n  2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py

Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.

Открыть доступ

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

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

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

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

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

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).

function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >

В другом подходе используется рекурсия. Помните, рекурсия – это когда функция вызывает саму себя. Вот второй вариант в псевдокоде:

function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >

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

Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.

Граничный и рекурсивный случай

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

// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

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

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >> 

Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

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

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

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

• рекурсия
• алгоритмы
• обучение программированию
• образование
• javascript
• перевод

Рекурсия

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

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

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

1. Кратко
2. Рекурсия в программировании
   1. Повторяющиеся операции
   2. Базовый случай
   1. Факториал с помощью цикла
   2. Факториал с помощью рекурсии
   1. Деревья
   2. Рекурсивный обход

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

   Кратко

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

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

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

   

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

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

   

   Треугольник состоит из 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 под-вызовов функции 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 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)    Скопировать Скопировано Не удалось скопировать   

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

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

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

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

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

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

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

   Как разместить блоки в ряд css