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

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

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

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести 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 значение факториала от предыдущего числа.

Теги:

• рекурсия
• задачи
• java

Добавить метки

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

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

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

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести 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 значение факториала от предыдущего числа.

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

Программирование ,

Совершенный код

• Tutorial

Рекурсия: см. рекурсия.

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

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

- Как она сложена?
- Превосходно! Только рука немного торчит из чемодана.

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

Def fib(n): if n<0: raise Exception("fib(n) defined for n>=0") if n>
приходится городить всевозможные грязные хаки, начиная от:

@memoized def fib(n): if n<0: raise Exception("fib(n) defined for n>=0") if n>1: return fib(n-1) + fib(n-2) return n
И заканчивая вообще:

Def fib(n): if n<0: raise Exception("fib(n) defined for n>=0") n0 = 0 n1 = 1 for k in range(n): n0, n1 = n1, n0+n1 return n0

Так что же такое рекурсия?

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

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

Теперь давайте рассмотрим классический пример: обход дерева в глубину. Впрочем нет, давайте рассмотрим другой пример: нам надо распечатать дерево выражений в форме обратной польской записи. То есть для дерева 1 мы хотим напечатать «2 2 +» а для дерева 2 «2 2 + 2 2 + *».

tex

\begin{tikzpicture} \node (is-root) {+} child { node {2} } child { node {2} }; \path (is-root) +(0,+0.5\tikzleveldistance) node {\textit{Tree 1}}; \end{tikzpicture} \begin{tikzpicture} \node (is-root) {*} child { node {+} child {node{2}} child {node{2}} } child { node {+} child {node{2}} child {node{2}} }; \path (is-root) +(0,+0.5\tikzleveldistance) node {\textit{Tree 2}}; \end{tikzpicture}

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

Class TreeNode(object): def __init__(self, value=None, children=): self.value = value self.children = children def printTree(node): for child in node.children: printTree(child) print node.value, def main(): tree1 = TreeNode("+", [ TreeNode(2), TreeNode(2) ]) tree2 = TreeNode("*", [ TreeNode("+", [ TreeNode(2), TreeNode(2) ]), TreeNode("+", [ TreeNode(2), TreeNode(2) ]) ]) print "Tree1:", printTree(tree1) print print "Tree2:", printTree(tree2) print if __name__ == "__main__": main()

Казалось бы, всё отлично! Код прекрасно работает до тех пор, пока дерево соответствует требованиям: любой узел имеет массив детей (возможно пустой) и какое-либо значение. Кто скажет какое еще требование к этому дереву?

Не буду томить. Требование: не сильно большая глубина дерева. Как так? А вот как:

Def buildTree(depth): root = TreeNode("1") node = root for k in range(depth): node = TreeNode("--", [ node ]) return node def depthTest(depth): tree = buildTree(depth) print "Tree of depth", depth, ":", printTree(tree) def main(): for d in range(10000): depthTest(d)
Запускаем, и ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Лезем в документацию, и обнаруживаем функцию sys.getrecursionlimit . А теперь давайте отойдём от мира интерпретируемых языков, и перейдём в мир языков, которые запускаются прямо на процессоре. Например, на C++.

Мысленно перепишем 1-в-1 этот код на С++ (оставлю эту задачу читателю в качестве разминки), и попробуем найти предел, когда приложение упрется в ограничение…

для ленивых

#include #include #include using namespace std; class TreeNode { public: string value_; vector children_; TreeNode(const string& value, const vector& children): value_(value), children_(children) {} virtual ~TreeNode() {} }; void printTree(const TreeNode* node) { for(auto i: node->children_) printTree(i); cout << node->value_ << " "; } TreeNode* buildTree(const int depth) { auto root = new TreeNode("1", {}); auto node = root; for(int i = 0; i children; children.push_back(node); node = new TreeNode("--", children); } return node; } void depthTest(const int depth) { auto tree = buildTree(depth); cout << "Tree of depth " << depth << ": "; printTree(tree); cout << endl; } int main() { for(int d=60000;; d+=16384) { depthTest(d); } }

Запускаем… «Bus error (core dumped)». Судя по gdb, в момент падения стек глубиной 104790 фреймов. А что произойдёт, если мы захотим печатать не просто подряд через пробелы, а выводить еще "{" и "}" вокруг выражений? Ну то есть для дерева 1 чтобы результатом было {2 2 +} а для дерева 2 - {{2 2 +}{2 2 +}*}? Перепишем…

Def printTree(node): opened = False for child in node.children: if not opened: print "{", opened = True printTree(child) print node.value, if opened: print "}",

Ничего не изменилось, по прежнему падает при попытке распечатать дерево глубиной 997. А теперь то же самое, но на плюсах… Опа. Глубина стека при падении - 87327. Стоп. Мы всего-то добавили одну локальную переменную, никак не влияющую на алгоритм и суть происходящего, а предельный размер дерева сократился на 17%! А теперь самое весёлое - всё это сильно зависит от опций компилятора, от того, на какой платформе выполняется, в какой ОС и с какими настройками.

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

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

Так в чем же проблема?

Использование рекурсивного алгоритма подразумевает использование практически не контролируемого ресурса: стека вызовов .

Во-1х, мы не можем точно знать сколько уже его использовано. Во-2х, мы не можем точно знать, сколько его еще осталось. В-3их мы не можем гарантировать доступность определённого размера этого ресурса к каждому вызову. В 4-ых, мы не можем фиксировать расход данного ресурса. Таким образом, мы попадаем в зависимость от ресурса, контролировать и распределять который чертовски сложно. В результате, мы не можем гарантировать каких либо характеристик данной функции/сервиса. Хорошо, если наш сервис работает в managed контексте: java, python, .net итп. Плохо, если сервис работает в неконтролируемой среде: javascript (с которым вообще всё плохо). Еще хуже, если сервис работает на C++, и глубина рекурсии зависит от данных, переданных пользователем.

Что же делать?

Если мы работаем не на микроконтроллере, о объёме стека можно не задумываться: для обычной цепочки вызовов его должно хватать. При условии, разумеется, что мы заботимся гигиене локальных переменных: большие объекты и массивы выделяются используя память (new/malloc). Однако использование рекурсии подразумевает, что вместо ограниченного количества вызовов, у нас их будет просто счетное.

Итак, чтобы избавиться от проблем, созданных рекурсией, можно сделать следующее (от простого к сложному):
- Жестко ограничить максимальный размер/формат/числа во входящих данных. Привет, zip бомбам и иже с ними - порой даже маленький входящий пакет может устроить большой переполох.
- Жестко ограничить максимальную глубину вызовов некоторым числом. Важно помнить, что это число должно быть ОЧЕНЬ небольшим. То есть порядка сотен. И обязательно добавить тесты, которые проверяют, что программа с этим максимальным числом не ломается. Причем с максимальным числом на всех возможных ветках исполнения (привет выделению локальных переменных по требованию). И не забывать проверять этот тест на разных опциях компилияции и после каждого билда.
- Жестко ограничить объём используемый стека. Используя сложные обходные маневры и знания о практической реализации исполнения в железе можно получить размер стека, который использован сейчас (типа взятия адреса локальной volatile переменной). В некоторых случаях (например, через libunwind в linux"е) можно получить так же доступный объём стека текущему потоку, и взять между ними разницу. При использовании подобного метода важно иметь тесты, проверяющие, что отсечение работает гарантированно и при всех вариантах входных данных - например, может получиться весело, если проверка идёт в одном методе, который рекурсивен через 3-4 других. И оно может упасть в промежуточном… Но только в режиме релиза, после inline"а некоторых функций, например. Впрочем, тут еще важны тесты на максимальную допустимую сложность, чтобы невзначай не отсечь часть корректных входных запросов, которыми клиенты реально пользуются.
- Лучший способ: избавиться от рекурсии .

И не лги, что ты волен и свят - Ты пленен и неволен.
Я раскрыл пред тобой небосвод!
Времена изменяют свой ход - Посмотри на ладони…

Беспредельная сладость свободы
Отринуть свободу
Сергей Калугин

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

Каноническая нерекурсивная реализацию обхода дерева в глубину:
def printTree(node): stack = [ (node, False, False) ] while len(stack)>0: i = len(stack)-1 node, visited, opened = stack[i] if not visited: for child in reversed(node.children): if not opened: print "{", opened = True stack.append((child, False, False)) visited = True stack[i] = (node, visited, opened) else: print node.value, if opened: print "}", del stack[i]
Как легко видеть, алгоритм не изменился, но вместо использования стека вызовов используется массив stack, размещенный в памяти, и хранящий как контекст обработки (в нашем случае - флаг opened) так и контекст обработки (в нашем случае - до или после обработки детей). В случаях, когда нужно что-то делать между каждым из рекурсивных вызовов, либо добавляются фазы обработки. Обратите внимание: это уже оптимизированный алгоритм, складывающий всех детей в стек сразу, и именно поэтому складывающий в обратном порядке. Это гарантирует сохранение того же порядка, что и у исходного нерекурсивного алгоритма.

Вот этот же код, только написанный «в лоб», сохраняя контекст (заодно, выводящий запятые между элементами):

Def printTree(node): stack = [ (node, 0) ] while len(stack)>0: i = len(stack)-1 node, phase = stack[i] if phase < len(node.children): child = node.children if phase == 0: print "{", if phase > 0: print ",", stack.append((child, 0)) stack[i] = (node, phase+1) else: print node.value, if phase>0: print "}", del stack[i]
Да, переход на безрекурсивные технологии не совсем бесплатен: мы платим периодически более дорогим - динамическим выделением памяти для организации стека. Впрочем, это окупается: в «ручной стек» сохраняются не вообще все локальные переменные, а только минимально необходимый контекст, размер которого уже можно контролировать. Вторая статья расходов: читабельность кода. Код, записанный в нерекурсивном виде несколько сложнее для восприятия за счет ветвлений от текущего состояния. Решение этой проблемы лежит уже в области организации кода: вынесение шагов в отдельные функции и грамотное их наименование.

Злоключение

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

А как не используете рекурсию вы?

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

Рекурсия

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

© Велигура А.В., кафедра экономической кибернетики, 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-элементов, и одни элементы могут входить в другие. Теги в тегах в тегах. И для эффективной обработки страницы браузеру требуется рекурсивно двигаться от уровня к уровню чтобы понять, в каком именно виде нужно вывести эти элементы на экран для пользователя.

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

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