Здравствуй Хабрахабр!

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

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

О рекурсии сказано много. Вот несколько хороших ресурсов:

• Рекурсия и рекурсивные задачи. Области применение рекурсии

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

Задачи

При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.

Как же решать задачи на рекурсию?

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

из сети

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

Для обоснования можно привести такие доводы.

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

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

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться

Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Итак рекурсивная функция состоит из

• Условие остановки или же Базовый случай
• Условие продолжения или Шаг рекурсии - способ сведения задачи к более простым.

Рассмотрим это на примере нахождения факториала :

Public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться повторять рекурсию? if (n == 1) { return 1; } // Шаг рекурсии / рекурсивное условие return recursion(n - 1) * n; } public static void main(String args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

Теги: Добавить метки

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

Что такое "рекурсия" вообще?

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

Что подразумевают под рекурсией в программировании?

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

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

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

Если читающий эти строки изучал программные циклы, то он, наверное, уже заметил схожесть между ними и рекурсией. В целом они действительно могут выполнять похожие или идентичные задания. С помощью рекурсии удобно делать имитацию работы цикла. Особенно это полезно там, где сами циклы использовать не очень удобно. Схема программной реализации не сильно различается у разных высокоуровневых языков программирования. Но всё же рекурсия в "Паскале" и рекурсия в С или другом языке имеет свои особенности. Может она быть успешно реализована и в низкоуровневых языках вроде "Ассемблера", но это является более проблематичным и затратным по времени.

Деревья рекурсии

Что такое "дерево" в программировании? Это конечное множество, состоящее как минимум из одного узла, который:

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

Другими словами: деревья содержат поддеревья, которые содержат ещё деревья, но в меньшем количестве, чем предыдущее дерево. Так продолжается до тех пор, пока в одном из узлов не останется возможности продвигаться далее, и это будет обозначать конец рекурсии. Есть ещё один нюанс насчет схематического изображения: обычные деревья растут снизу вверх, а в программировании они рисуются наоборот. Узлы, не имеющие продолжения, называются конечными узлами. Для удобства обозначения и для удобства используется генеалогическая терминология (предки, дети).

Зачем она применяется в программировании?

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

Отличия рекурсии в различных языках программирования

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

Рекурсия - это легко. Как просто запомнить содержание статьи?

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

От лат recursio (возвращение). В общем случае так называется процесс повторения элементов «самоподобным образом».

Яркий пример рекурсии - матрёшки. Рекурсивное определение: «матрёшка - это разъемная пустотелая деревянная кукла, содержащая внутри матрёшку меньшего размера». Вот такая рекурсия по-русски. И если бы не предел возможностей мастеров, идеальная матрёшка уходила бы в глубь себя до атомарного уровня. А то и глубже. Просто у Левши не нашлось мелкоскопа достаточной силы. Верхний предел теоретически тоже не ограничен, но баобабы подходящего размера на нашей планете не растут. В общем, по техническим причинам рекурсия должна быть конечной.

В программировании (как и в математике) рекурсия - процесс вызова функцией самой себя (прямая рекурсия), либо вызов изнутри функции A функции B, которая в свою очередь содержит вызов функции A (косвенная или взаимная рекурсия). Разумеется, рекурсивные вызовы должны иметь выполнимое условие завершения, иначе такая программа «зависнет», как в бесконечном цикле - но, в отличие от бесконечного цикла, при бесконечной рекурсии она аварийно завершится переполнением стека.

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

Самый надоевший пример рекурсии в математическом программировании - вычисление факториала. Не будем изменять славным традициям. Для тех, кто еще не проходил: N! (факториал N) - это произведение всех натуральных чисел от единицы до N (факториал нуля равен 1).
Можно тупо перемножать числа от 1 до N в цикле. А можно соорудить функцию factorial(n), которая будет содержать условие и вызов самой себя. Если n равно единице, то функция возвращает значение 1, иначе возвращает значение n, умноженное на factorial(n-1).
Зарисовка на PHP

Function factorial($n) { if ($n == 1) { return 1; } else { return intval($n * factorial($n - 1)); } }

Практические применения рекурсии

«Ну, и зачем это здесь нужно?» - спросит нас нетерпеливый юный читатель - «Чушь научная, занудство, факториалы всякие… А практически к чему эту рекурсию приложить?»
«К подбитому глазу веб-программированию» - без колебаний ответим мы. И тут же это обоснуем.

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

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

Рекурсия в поисковых системах

Да, именно так. Поисковым системам от рекурсии тоже некуда деваться. С тех пор, как был заведен обычай мерить авторитетность сайта (документа) количеством ссылок, поисковики попались в рекурсивную ловушку, и пусть они блуждают в ней вечно (это искреннее доброе пожелание автора). Ссылочный «вес» сайта складывается из маленьких кусочков «веса» от всех тех, которые на него ссылаются. Чтобы вычислить этот вес для A, на которого ссылаются B, C и D, надо обсчитать их вес, который в свою очередь передается всякими другими, вес которых тоже нужно обсчитывать… и так по всей учтенной в поисковике Сети. Совершенно рекурсивная задачка. А вы говорите - сплошная теория. Самая что ни на есть реальная практика.

Рекурсивный PageRank от Google

Свой базовый алгоритм расчета PageRank создатели Google опубликовали давно. И как бы он с тех пор ни менялся, сколько бы его ни дополняли усовершенствованиями, основа остается прежней. Нельзя узнать, какую величину PageRank страница B передает по ссылке странице A, пока мы не сосчитали, какой PageRank получила страница B от всех прочих страниц, которые на нее сослались, а этого нельзя узнать, пока мы не посчитаем PageRank этих страниц… продолжать? Наверное, уже не надо. Это опять Она - Её Величество Рекурсия .

В осточноукраинский национальный университет имени Владимира Даля

Рекурсия

Информатика и компьютерная техника

© Велигура А.В., кафедра экономической кибернетики, 2004

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

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

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

Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (direct recursion) выглядит примерно так:

Function Factorial(num As Long) As Long

Factorial = num * Factorial(num - 1)

В случае косвенной рекурсии (indirectrecursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

Private Sub Pong(num As Integer)

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

Private Sub DrawTree()

Нарисовать "ствол"

Нарисовать дерево меньшего размера, повернутое на -45 градусов

Нарисовать дерево меньшего размера, повернутое на 45 градусов

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

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

1. Опасности рекурсии

   1. Бесконечная рекурсия

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

Private Function BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)

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

Private Function BadFactorial2(num As Double) As Double

BadFactorial2 = 1

BadFactorial2 = num * BadFactorial2(num-1)

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

Private Function BadFib(num As Double) As Double

BadFib = BadPib(num - 1) + BadFib (num - 2)

И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших значенияхN. Наибольшее возможное значениеN, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.

Private Function BigAdd(N As Double) As Double

If N <= 1 Then

BigAdd=N + BigAdd(N - 1)

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

Представляем функции

• Можно представить функции как чёрные коробки: коробка забирает объект, производит внутри какие-то действия, а потом выплёвывает что-то новое
  • Некоторые функции ничего не забирают (не принимают аргументы), некоторые вообще ничего не делают (они пустые), некоторые не возвращают значения.
  • Наш surfaceAreaCalculator принимает один аргумент (radius), вычисляет площадь поверхности и возвращает результат этого вычисления.
• Функции могут вызывать другие функции
• surfaceAreaCalculator может вызывать функцию square , чтобы получить радиус, возведённый в квадрат, вместо того, чтобы умножать радиус на радиус.
• Мы пишем функции, чтобы облегчить жизнь:
  • такой код легче понимать
  • функции могут переиспользоваться несколько раз

Сравните:

Const surfaceOfMars = surfaceAreaCalculator(3390); // это "ЧТО", в таком виде легче понять суть const surfaceOfMars = 4 * 3.14 * 3390 * 3390; // это "КАК"

Две функции вместе:

const surfaceAreaCalculator = (radius) => { return 4 * 3.14 * square(radius); } const square = (num) => { return num * num; }

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

• Определение функции - это описание коробки
• Оригинал коробки формируется при вызове функции
• Когда функция вызывает сама себя, создаётся новая идентичная коробка

Перестановки:

• Количество способов перестановки n объектов равно n! (permutations)
• n! определяется таким способом: если n = 1, то n! = 1 ; если n > 0, то n! = n * (n-1)!

Функция, вычисляющая факториал:

Const factorial = (n) =>

Требования рекурсии

1. Простой базовый случай или терминальный сценарий. Простыми словами, когда остановиться. В нашем примере это была 1: мы остановили вычисление факториала, когда достигли 1.
2. Правило двигаться по рекурсии, углубляться. В нашем случае, это было n * factorial(n-1) .

Ожидание умножения

Ничего не умножается, пока мы спускаемся к базовому случаю factorial(1) . Затем мы начинаем подниматься обратно, по одному шагу.

Примечание

Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 - это, в любом случае - 1.

Просто ради забавы

У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска;-)

Опциональные видео

Транскрипт урока

У нас уже есть функция surfaceAreaCalculator , которая принимает один аргумент - радиус - и возвращает площадь поверхности соответствующей сферы, используя формулу 4 * pi * r 2. Помните, мы можем представить функции ящиками: кладём что-то в ящик, она производит какие-то действия и выплёвывает результат.

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

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

Ещё польза в том, что теперь код проще понять. Сравните это:

Const surfaceOfMars = surfaceAreaCalculator(3390);

Const surfaceOfMars = 4 * 3.14 * 3390 * 3390;

Первый вариант намного приятней и проще, особенно для того, кто только что увидел этот код. Первый вариант отвечает на вопрос "что", второй - на вопрос "как".

Const surfaceAreaCalculator = (radius) => { return 4 * 3.14 * square(radius); }

Вместо умножения радиуса на радиус, мы вызовем функцию вычисления квадрата и передадим ей радиус. Очевидно - всё, что делает функция вычисления квадрата, это "принимает число и возвращает его квадрат";

Const square = (num) => { return num * num; }

Давайте отследим шаги и посмотрим, что происходит, когда мы запускаем нашу программу. Мы создаём константу surfaceOfMars и пытаемся сохранить в нее значение, которое возвращает функция surfaceAreaCalculator , когда она вызывается с числом 3390 в качестве аргумента.

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

square хочет умножить n на n и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри surfaceAreaCalculator , который в прямом смысле ждал, пока функция square закончит своё дело. И теперь у нас есть результат вызова square . Он заменяет вызов, поэтому теперь становится возможным завершить умножение и вернуть ответ.

Ответ возвращается и сохраняется в surfaceOfMars .

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

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

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

Вообще, существует n! вариантов перестановки n книг. Факториал означает - умножить все числа от 1 до n. Так что, 3! это 1 * 2 * 3. Давайте напишем функцию факториала.

Const factorial = (n) => { return 1 * 2 * 3 * 4; // oй... }

Ой, подождите. Мы не знаем значение n изначально, в этом вся проблема. Хмм… Как там делается в математике?

А, хорошо, у них там есть два варианта: если n равно 1, тогда факториал - 1, это просто. Но если n не равно 1, тогда факториал - n*(n-1)!

Давайте попробуем вот так:

Const factorial = (n) => { if (n === 1) { return 1; } else { return n * factorial(n-1); } } const answer = factorial(3);

Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

Может тут что-то не так? Вообще-то нет! Всё дело в том, что сама по себе функция - это не ящик, это его описание. Когда вы вызываете функцию, тогда создается ящик, а после того, как функция выполнилась, ящик самоуничтожается. Поэтому когда вы вызываете ту же самую функцию из неё самой, просто создается ещё один ящик.

Давайте это отследим: мы вызываем factorial(3) . 3 это не 1, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может - ей нужно знать второе число, для чего она вызывает factorial(3-1) или factorial(2) .

Формируется новый идентичный ящик factorial , он принимает число 2, это не 1, так что он пробует произвести умножение и вернуть ответ, но не может - ему нужно знать второе число, поэтому он вызывает factorial(1) .

Формируется новый идентичный ящик factorial , он принимает число 1, и этот ящик уже может мгновенно вернуть ответ - он возвращает 1.

1 возвращается в предыдущий ящик, умножается на 2 и ответ "2" возвращается в предыдущий ящик, умножается на 3 и ответ "6" возвращается во внешний мир и сохраняется в константе answer .

Всё это и есть рекурсия: что-то описывается через самого себя, содержит себя в своём описании. Когда дело касается математики или программирования, требуется два условия:

1. Простой базовый случай или терминальный сценарий. Это точка в которой нужно остановиться. В нашем примере это 1: мы остановили вычисление факториала, когда получили 1.
2. Правило передвижения по рекурсии, углубление. В нашем случае это было n * factorial(n-1) .

Давайте проследим шаги ещё раз, но с другой точки зрения, не заглядывая в ящики. Вот как это выглядит пошагово:

Factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;

Умножение не происходит пока мы спускаемся до базового случая функции factorial(1) . А затем мы возвращаемся наверх, производя одно умножение за один шаг.

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

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

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

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