Какая структура данных используется для осуществления рекурсии. Рекурсия. Две функции вместе
Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:
- структуры данных:
- граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
- строка состоит из первого символа и подстроки (меньшей строки);
- шаблоны проектирования, например . Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. Детально рекурсивные шаблоны изучил Мак-Колм Смит, выделив в своей книге общий шаблон проектирования — Recursion ;
- рекурсивные функции (алгоритмы) выполняют вызов самих себя.
Статья посвящена анализу трудоемкости рекурсивных алгоритмов, приведены необходимые математические сведения, рассмотрены примеры. Кроме того, описана возможность замены рекурсии циклом, хвостовая рекурсия.
Примеры рекурсивных алгоритмов
Рекурсивный алгоритм всегда разбивает задачу на части, которые по своей структуре являются такими же как исходная задача, но более простыми. Для решения подзадач функция вызывается рекурсивно, а их результаты каким-либо образом объединяются. Разделение задачи происходит лишь тогда, когда ее не удается решить сразу (она является слишком сложной).
Например, задачу обработки массива нередко можно свести к обработке его частей. Деление на части выполняется до тех пор, пока они не станут элементарными, т.е. достаточно простыми чтобы получить результат без дальнейшего упрощения.
Поиск элемента массива
начало; search(array, begin, end, element) ; выполняет поиск элемента со значением element в массиве array между индексами begin и end если begin > end результат:= false; элемент не найден иначе если array = element результат:= true; элемент найден иначе результат:= search(array, begin+1, end, element) конец; вернуть результатАлгоритм делит исходный массив на две части — первый элемент и массив из остальных элементов. Выделяется два простых случая, когда разделение не требуется — обработаны все элементы или первый элемент является искомым.
В алгоритме поиска разделять массив можно было бы и иначе (например пополам), но это не сказалось бы на эффективности. Если массив отсортирован — то его деление пополам целесообразно, т.к. на каждом шаге количество обрабатываемых данных можно сократить на половину.
Двоичный поиск в массиве
Двоичный поиск выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения либо левая, либо правая части могут быть «отброшены».
Начало; binary_search(array, begin, end, element) ; выполняет поиск элемента со значением element ; в массиве упорядоченном по возрастанию массиве array ; между индексами begin и end если begin > end конец; вернуть false - элемент не найден mid:= (end + begin) div 2; вычисление индекса элемента посередине рассматриваемой части массива если array = element конец; вернуть true (элемент найден) если array < element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат
Вычисление чисел Фибоначчи
Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n > 2\).
Начало; fibonacci(number) если number = 0 конец; вернуть 0 если number = 1 конец; вернуть 1 fib_1:= fibonacci(number-1) fib_2:= fibonacci(number-2) результат:= fib_1 + fib_2 конец; вернуть результат
Быстрая сортировка (quick sort)
Алгоритм быстрой сортировки на каждом шаге выбирает один из элементов (опорный) и относительно него разделяет массив на две части, которые обрабатываются рекурсивно. В одну часть помещаются элементы меньше опорного, а в другую — остальные.
Блок-схема алгоритма быстрой сортировки
Сортировка слиянием (merge sort)
В основе алгоритма сортировки слиянием лежит возможность быстрого объединения упорядоченных массивов (или списков) так, чтобы результат оказался упорядоченным. Алгоритм разделяет исходный массив на две части произвольным образом (обычно пополам), рекурсивно сортирует их и объединяет результат. Разделение происходит до тех пор, пока размер массива больше единицы, т.к. пустой массив и массив из одного элемента всегда отсортированы.
Блок схема сортировки слияниемНа каждом шаге слияния из обоих списков выбирается первый необработанный элемент. Элементы сравниваются, наименьший из них добавляется к результату и помечается как обработанный. Слияние происходит до тех пор, пока один из списков не окажется пуст.
Начало; merge(Array1, Size1, Array2, Size2) ; исходные массивы упорядочены; в результат формируется упорядоченный массив длины Size1+Size2 i:= 0, j:= 0 вечный_цикл если i >= Size1 дописать элементы от j до Size2 массива Array2 в конец результата выход из цикла если j >= Size2 дописать элементы от i до Size1 массива Array1 в конец результата выход из цикла если Array1[i] < Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Array2[j]) результат := Array2[j] j:= j + 1 конец; вернуть результат
Анализ рекурсивных алгоритмов
При рассчитывается трудоемкость итераций и их количество в наихудшем, наилучшем и среднем случаях . Однако не получится применить такой подход к рекурсивной функции, т.к. в результате будет получено рекуррентное соотношение. Например, для функции поиска элемента в массиве:
\(
\begin{equation*}
T^{search}_n = \begin{cases}
\mathcal{O}(1) \quad &\text{$n = 0$} \\
\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) \quad &\text{$n > 0$}
\end{cases}
\end{equation*}
\)
Рекуррентные отношения не позволяют нам оценить сложность — мы не можем их просто так сравнивать, а значит, и сравнивать эффективность соответствующих алгоритмов. Необходимо получить формулу, которая опишет рекуррентное отношение — универсальным способом сделать это является подбор формулы при помощи метода подстановки, а затем доказательство соответствия формулы отношению методом математической индукции.
Метод подстановки (итераций)
Заключается в последовательной замене рекуррентной части в выражении для получения новых выражений. Замена производится до тех пор, пока не получится уловить общий принцип и выразить его в виде нерекуррентной формулы. Например для поиска элемента в массиве:
\(
T^{search}_n = \mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) =
2\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-2}) =
3\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-3})
\)
Можно предположить, что \(T^{search}_n = T^{search}_{n-k} + k\times\mathcal{O}(1)\), но тогда \(T^{search}_n = T^{search}_{0} + n\times\mathcal{O}(1) = \mathcal{O}(n)\).
Мы вывели формулу, однако первый шаг содержит предположение, т.е. не имеется доказательства соответствия формулы рекуррентному выражению — получить доказательство позволяет метод математической индукции.
Метод математической индукции
Позволяет доказать истинность некоторого утверждения (\(P_n\)), состоит из двух шагов:
- доказательство утверждения для одного или нескольких частных случаев \(P_0, P_1, …\);
- из истинности \(P_n\) (индуктивная гипотеза) и частных случаев выводится доказательство \(P_{n+1}\).
Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска (\(T^{search}_n = (n+1)\times\mathcal{O}(1)\)):
- \(T^{search}_{1} = 2\times\mathcal{O}(1)\) верно из условия (можно подставить в исходную рекуррентную формулу);
- допустим истинность \(T^{search}_n = (n+1)\times\mathcal{O}(1)\);
- требуется доказать, что \(T^{search}_{n+1} = ((n+1)+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
- подставим \(n+1\) в рекуррентное соотношение: \(T^{search}_{n+1} = \mathcal{O}(1) + T^{search}_n\);
- в правой части выражения возможно произвести замену на основании индуктивной гипотезы: \(T^{search}_{n+1} = \mathcal{O}(1) + (n+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
- утверждение доказано.
Часто, такое доказательство — достаточно трудоемкий процесс, но еще сложнее выявить закономерность используя метод подстановки. В связи с этим применяется, так называемый, общий метод .
Общий (основной) метод решения рекуррентных соотношений
Общий метод не является универсальным, например с его помощью невозможно провести оценку сложности приведенного выше алгоритма вычисления чисел Фибоначчи. Однако, он применим для всех случаев использования подхода «разделяй и властвуй» :
\(T_n = a\cdot T(\frac{n}{b})+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).
Уравнения такого вида получаются если исходная задача разделяется на a подзадач, каждая из которых обрабатывает \(\frac{n}{b}\) элементов. \(f_n\) — трудоемкость операций разбиения задачи на части и комбинирование решений. Помимо вида соотношения, общий метод накладывает ограничения на функцию \(f_n\), выделяя три случая:
- \(\exists \varepsilon > 0: f_n = \mathcal{O}(n^{\log_b a — \varepsilon}) \Rightarrow T_n = \Theta(n^{\log_b a})\);
- \(f_n = \Theta(n^{\log_b a}) \Rightarrow T_n = \Theta(n^{\log_b a} \cdot \log n)\);
- \(\exists \varepsilon > 0, c < 1: f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)\).
Правильность утверждений для каждого случая доказана формально . Задача анализа рекурсивного алгоритма теперь сводится к определению случая основной теоремы, которому соответствует рекуррентное соотношение.
Анализ алгоритма бинарного поиска
Алгоритм разбивает исходные данные на 2 части (b = 2), но обрабатывает лишь одну из них (a = 1), \(f_n = 1\). \(n^{\log_b a} = n^{\log_2 1} = n^0 = 1\). Функция разделения задачи и компоновки результата растет с той же скоростью, что и \(n^{\log_b a}\), значит необходимо использовать второй случай теоремы:
\(T^{binarySearch}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(1 \cdot \log n) = \Theta(\log n)\).
Анализ алгоритма поиска
Рекурсивная функция разбивает исходную задачу на одну подзадачу (a = 1), данные делятся на одну часть (b = 1). Мы не можем использовать основную теорему для анализа этого алгоритма, т.к. не выполняется условие \(b > 1\).
Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность \(\mathcal{O}(1)\). Тогда \(T^{search}_n = n \cdot \mathcal{O}(1) = \mathcal{O}(n)\).
Анализ алгоритма сортировки слиянием
Исходные данные разделяются на две части, обе из которых обрабатываются: \(a = 2, b = 2, n^{\log_b a} = n\).
При обработке списка, разделение может потребовать выполнения \(\Theta(n)\) операций, а для массива — выполняется за постоянное время (\(\Theta(1)\)). Однако, на соединение результатов в любом случае будет затрачено \(\Theta(n)\), поэтому \(f_n = n\).
Используется второй случай теоремы: \(T^{mergeSort}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(n \cdot \log n)\).
Анализ трудоемкости быстрой сортировки
В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных — для массива \(\mathcal{O}(n)\), для связного списка \(\mathcal{O}(1)\). \(a = 2, b = 2, f_n = b\), значит сложность алгоритма будет такой же как у сортировки слиянием: \(T^{quickSort}_n = \mathcal{O}(n \cdot \log n)\).
Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда \(b = 1\), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части (\(\mathcal{O}(n)\)) — значит сложность алгоритма \(T^{quickSort}_n = \mathcal{O}(n^2)\).
При анализе быстрой сортировки методом подстановки, пришлось бы также рассматривать отдельно наилучший и наихудший случаи.
Хвостовая рекурсия и цикл
Анализ трудоемкости рекурсивных функций значительно сложнее аналогичной оценки циклов, но основной причиной, по которой циклы предпочтительнее являются высокие затраты на вызов функции.
После вызова управление передается другой функции. Для передачи управления достаточно изменить значение регистра программного счетчика, в котором процессор хранит номер текущей выполняемой команды — аналогичным образом передается управление ветвям алгоритма, например, при использовании условного оператора. Однако, вызов — это не только передача управления, ведь после того, как вызванная функция завершит вычисления, она должна вернуть управление в точку, и которой осуществлялся вызов, а также восстановить значения локальных переменных, которые существовали там до вызова.
Для реализации такого поведения используется стек (стек вызовов, call stack) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.
В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше . В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.
Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра
, который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
\(fact_n = n \cdot fact(n-1) \\
fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
fact_n = factTail_{n, 1} \\
\\
factTail_{n, accumulator} = factTail(n-1, accumulator \cdot n)\\
factTail_{3, 1} = factTail_{2, 3} = factTail_{1, 6} = factTail_{0, 6} = 6
\)
В качестве более сложного примера рассмотрим функцию вычисления чисел Фибоначчи. Основная функция вызывает вспомогательную,использующую метод накапливающего параметра, при этом передает в качестве аргументов начальное значение итератора и два аккумулятора (два предыдущих числа Фибоначчи).
Начало; fibonacci(number) вернуть fibonacci(number, 1, 1, 0) конец начало; fibonacci(number, iterator, fib1, fib2) если iterator == number вернуть fib1 вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1) конец
Функция с накапливающим параметром возвращает накопленный результат, если рассчитано заданное количество чисел, в противном случае — увеличивает счетчик, рассчитывает новое число Фибоначчи и производит рекурсивный вызов. Оптимизирующие компиляторы могут обнаружить, что результат вызова функции без изменений передается на выход функции и заменить его циклом. Такой прием особенно актуален в функциональных и логических языках программирования, т.к. в них программист не может явно использовать циклические конструкции.
Литература
- Многопоточный сервер Qt. Пул потоков. Паттерн Decorator[Электронный ресурс] – режим доступа : https://сайт/archives/1390. Дата обращения: 21.02.2015.
- Джейсон Мак-Колм Смит : Пер. с англ. - М. : ООО “И.Д. Вильямс”, 2013. - 304 с.
- Скиена С. Алгоритмы. Руководство по разработке.-2-е изд.: пер. с англ.-СПб.:БХВ-Петербург, 2011.-720с.: ил.
- Васильев В. С. Анализ сложности алгоритмов. Примеры [Электронный ресурс] – режим доступа: https://сайт/archives/1660. Дата обращения: 21.02.2015.
- А.Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы, М., Вильямс, 2007.
- Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.
- Сергиевский Г.М. Функциональное и логическое программирование: учеб. пособие для студентов высш. учеб. заведений / Г.М. Сергиевский, Н.Г. Волченков. - М.: Издательский центр «Академия», 2010.- 320с.
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи мы уже решали, но с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!
"stdafx.h"
#include
// код Code::Blocks
// код Dev-C++
// factorial.cpp: определяет точку входа для консольного приложения.
#include
В строках 7, 9, 21 объявлен тип данных unsigned long int , так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение. В коде объявлено больше операторов, чем нужно, для нахождения n!. Это сделано для того, чтобы, отработав, программа показала, что происходит на каждом шаге рекурсивных вызовов. Обратите внимание на выделенные строки кода, строки 23, 24, 28 — это рекурсивное решение n!. Строки 23, 24 являются базовым решением рекурсивной функции, то есть, как только значение в переменной f будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 28 функция factorial() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения. Результат работы программы (см. Рисунок 1).
Enter n!: 5 Step 1 Result= 0 Step 2 Result= 0 Step 3 Result= 0 Step 4 Result= 0 5!=120
Рисунок 1 — Рекурсия в С++
По результату работы программы хорошо виден каждый шаг и результат на каждом шаге равен нулю, кроме последнего рекурсивного обращения. Необходимо было вычислить пять факториал. Программа сделала четыре рекурсивных обращения, на пятом обращении был найден базовый случай. И как только программа получила решение базового случая, она порешала предыдущие шаги и вывела общий результат. На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.
Рисунок 2 — Рекурсия в С++
Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.
Переделаем программу нахождения факториала так, чтобы получить таблицу факториалов. Для этого объявим цикл for , в котором будем вызывать рекурсивную функцию.
// код Code::Blocks // код Dev-C++ // factorial.cpp: определяет точку входа для консольного приложения.
#include В строках 16 — 19
объявлен цикл, в котором вызывается рекурсивная функция. Всё ненужное в программе закомментированно. Запустив программу, нужно ввести значение, до которого необходимо вычислить факториалы. Результат работы программы показан на рисунке 3. Enter n!: 14
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=6227020800
14!=87178291200 Рисунок 3 — Рекурсия в С++ Теперь видно, насколько быстро возрастает факториал, кстати говоря, уже результат 14! не правильный, это и есть последствия нехватки размера типа данных. Правильное значение 14! = 87178291200. Рассмотрим ещё одну типичную задачу — нахождение чисел Фибоначчи, используя рекурсию. Далее приведен код рекурсивного решения такой задачи. Вводим в ком строке порядковый номер числа из ряда Фибоначчи, и программа найдёт все числа из ряда Фибоначчи порядковые номера которых меньше либо равны введённого. // fibonacci.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include // код Code::Blocks // код Dev-C++ // fibonacci.cpp: определяет точку входа для консольного приложения.
#include В строке 6
подключена библиотека Enter number from the Fibonacci series: 30
1 = 0
2 = 1
3 = 1
4 = 2
5 = 3
6 = 5
7 = 8
8 = 13
9 = 21
10 = 34
11 = 55
12 = 89
13 = 144
14 = 233
15 = 377
16 = 610
17 = 987
18 = 1597
19 = 2584
20 = 4181
21 = 6765
22 = 10946
23 = 17711
24 = 28657
25 = 46368
26 = 75025
27 = 121393
28 = 196418
29 = 317811
30 = 514229 Рисунок 4 — Рекурсия в С++ Решение сводится к разбиению сложной задачи к двум более простым. Например, чтобы найти третье число из ряда Фибоначчи, необходимо сначала найти первое и второе, а потом сложить их. Первое число является частным случаем и равно 0 (нулю), второе число также является частным случаем и равно 1. Следовательно, третье число из ряда Фибоначчи равно сумме первого и второго = 1. Приблизительно так же рассуждала запрограммированная нами рекурсивная функция поиска чисел ряда Фибоначчи. Разработаем ещё одну рекурсивную программу, решающую классическую задачу — «Ханойская башня». Даны три стержня, на одном из которых находится стопка n-го количества дисков, причём диски имеют не одинаковый размер (диски различного диаметра) и расположены таким образом, что по мере прохождения, сверху вниз по стержню диаметр дисков постепенно увеличивается. То есть диски меньшего размера должны лежать только на дисках большего размера. Необходимо переместить эту стопку дисков с начального стержня на любой другой из двух оставшихся (чаще всего это третий стержень). Один из стержней использовать как вспомогательный. Перемещать можно только по одному диску, при этом диск большего размера никогда не должен находиться над диском меньшего размера. Допустим необходимо переместить три диска с первого стержня на третий, значит второй стержень вспомогательный. Визуальное решение данной задачи реализовано во Flash. Нажмите на кнопку start , чтобы запустить анимацию, кнопку stop , чтобы остановить. Программу надо написать для n-го количества дисков. Так как мы решаем данную задачу рекурсивно, то для начала необходимо найти частные случаи решения. В данной задаче частный случай только один – это когда необходимо переместить всего один диск, и в этом случае даже вспомогательный стержень не нужен, но на это просто не обращаем внимания. Теперь необходимо организовать рекурсивное решение, в случае, если количество дисков больше одного. Введём некоторые обозначения, для того, чтоб не писать лишнего:
<Б>
— стержень, на котором изначально находятся диски (базовый стержень); Далее, при описании алгоритма решения задачи будем использовать эти обозначения. Чтобы переместить три диска с <Б>
на<Ф>
нам необходимо сначала переместить два диска с <Б>
на <П>
а потом переместить третий диск(самый большой) на<Ф>
, так как <Ф>
свободен. Длятого, чтобы переместить n
дисков с <Б>
на <Ф>
нам необходимо сначала переместить n-1
дисков с <Б>
на <П>
а потом переместить n-й диск(самый большой) на <Ф>
, так как <Ф>
свободен. После этого необходимо переместить n-1
дисков с <П>
на <Ф>
, при этом использовать стержень <Б>
как вспомогательный. Эти три действия и есть весь рекурсивный алгоритм. Этот же алгоритм на псевдокоде: // hanoi_tower.cpp: определяет точку входа для консольного приложения.
// Программа, рекурсивно решающая задачу "Ханойская башня"
#include "stdafx.h"
#include // код Code::Blocks // код Dev-C++ // hanoi_tower.cpp: определяет точку входа для консольного приложения.
// Программа, рекурсивно решающая задачу "Ханойская башня"
#include На рисунке 5 показан пример работы рекурсивной программы Ханойская башня. Сначала мы ввели количество дисков равное трём, потом ввели базовый стержень (первый), и обозначили конечный стержень (третий). Автоматически второй стержень стал вспомогательным. Программа выдала такой результат, что он полностью совпадает с анимационным решением данной задачи. Enter of numbers of disks: 3
Enter the number of basic rod: 1
Enter the number of final rod: 3
1) 1 -> 3
2) 1 -> 2
3) 3 -> 2
4) 1 -> 3
5) 2 -> 1
6) 2 -> 3
7) 1 -> 3 Рисунок 5 — Рекурсия в С++ Из рисунка видно, что сначала перемещается диск со стержня один на стержень три, потом со стержня один на стержень два, со стержня три на стержень
два и т. д. То есть программа всего лишь выдает последовательность перемещений дисков и минимальное количество шагов, за которые будут перемещены все диски.
Все эти задачи можно было решить итеративно. Возникает вопрос: “Как лучше решать, итеративно или рекурсивно?”. Отвечаю: “Недостаток рекурсии в том, что она затрачивает значительно больше компьютерных ресурсов, нежели итерация. Это выражается в большой нагрузке, как на оперативную память, так и на процессор. Если очевидно решение той или иной задачи итеративным способом, то им и надо воспользоваться иначе, использовать рекурсию!” В зависимости от решаемой задачи сложность написания программ изменяется при использовании того или иного метода решения. Но чаще задача, решённая рекурсивным методом с точки зрения читабельности кода, куда понятнее и короче. Прикладное программирование всегда занимается решением прикладных задач путем прикладывания усилий программиста для достижения результата в неидеальных условиях. Именно исходя из неидеальности этого мира и ограниченности ресурсов и складывается потребность в программистах: кому-то ведь надо помогать теоретикам упихать их стройную и красивую теорию в практику. 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
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)
Мысленно перепишем 1-в-1 этот код на С++ (оставлю эту задачу читателю в качестве разминки), и попробуем найти предел, когда приложение упрется в ограничение… для ленивых
#include 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++, и глубина рекурсии зависит от данных, переданных пользователем. Итак, чтобы избавиться от проблем, созданных рекурсией, можно сделать следующее (от простого к сложному): Беспредельная сладость свободы Каноническая нерекурсивная реализацию обхода дерева в глубину: Вот этот же код, только написанный «в лоб», сохраняя контекст (заодно, выводящий запятые между элементами): 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 градусов Хотя рекурсия и может упростить понимание
некоторых проблем, люди обычно не мыслят
рекурсивно. Они обычно стремятся разбить
сложные задачи на задачи меньшего
объема, которые могут быть выполнены
последовательно одна за другой до
полного завершения. Например, чтобы
покрасить изгородь, можно начать с ее
левого края и продолжать двигаться
вправо до завершения. Вероятно, во время
выполнения подобной задачи вы не думаете
о возможности рекурсивной окраски -
вначале левой половины изгороди, а затем
рекурсивно - правой. Для того чтобы думать рекурсивно, нужно
разбить задачу на подзадачи, которые
затем можно разбить на подзадачи меньшего
размера. В какой‑то момент подзадачи
становятся настолько простыми, что
могут быть выполнены непосредственно.
Когда завершится выполнение подзадач,
большие подзадачи, которые из них
составлены, также будут выполнены.
Исходная задача окажется выполнена,
когда будут все выполнены образующие
ее подзадачи. Наиболее
очевидная опасность рекурсии заключается
в бесконечной рекурсии. Если неправильно
построить алгоритм, то функция может
пропустить условие остановки рекурсии
и выполняться бесконечно. Проще всего
совершить эту ошибку, если просто забыть
о проверке условия остановки, как это
сделано в следующей ошибочной версии
функции факториала. Поскольку функция
не проверяет, достигнуто ли условие
остановки рекурсии, она будет бесконечно
вызывать сама себя. 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на диске с примерами демонстрирует этот
алгоритм. Проверьте, насколько большое
входное значение вы можете ввести в
этой программе до того, как наступит
переполнение стека на вашем компьютере. Здравствуй Хабрахабр! В этой статье речь пойдет о задачах на рекурсию и о том как их решать. В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). О рекурсии сказано много. Вот несколько хороших ресурсов: из сети
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно. Для обоснования можно привести такие доводы. Для начала можно вспомнить определение рекурсии и итерации. Рекурсия - это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация - это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ. После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий - итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно - завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма. Задача по приведению рекурсии к итеративному подходу симметрична. Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче. Более подробно с этим можно познакомиться Итак рекурсивная функция состоит из 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 значение факториала от предыдущего числа. Теги:
<П>
— вспомогательный или промежуточный стержень;
<Ф>
— финальный стержень – стержень, на который необходимо переместить диски.
n-1
переместить на <П>
n
переместить на <Ф>
n-1
переместить с <П>
на <Ф>
, при этом использовать <Б>
как вспомогательныйРекурсия: см. рекурсия.
Все программисты делятся на 11 2 категорий: кто не понимает рекурсию, кто уже понял, и кто научился ею пользоваться. В общем, гурилка из меня исключительно картонный, так что постигать Дао Рекурсии тебе, читатель, всё равно придётся самостоятельно, я лишь постараюсь выдать несколько волшебных пенделей в нужном направлении. - Как она сложена?
- Превосходно! Только рука немного торчит из чемодана.
Именно пытаясь разместить стройную теорию алгоритма в жесткий рюкзак реальных ресурсов и приходится постоянно кроить по живому, перепаковывать, и вместо красивых и стройных определений Фибоначчи:
приходится городить всевозможные грязные хаки, начиная от:
И заканчивая вообще:Так что же такое рекурсия?
Рекурсия, по сути, это доказательство по индукции. Мы рассказываем, как получить результат для некоего состояния, предполагая что у нас есть результат для другого набора состояний, так же рассказываем, как получить результат в тех состояниях, к которым всё скатывается так или иначе.Если вы ждете гостей и вдруг заметили на своем костюме пятно, не огорчайтесь. Это поправимо.
Например, пятна от растительного масла легко выводятся бензином. Пятна от бензина легко снимаются раствором щелочи.
Пятна от щелочи исчезают от уксусной эссенции. Следы от уксусной эссенции надо потереть подсолнечным маслом.
Ну, а как выводить пятна от подсолнечного масла, вы уже знаете...
Теперь давайте рассмотрим классический пример: обход дерева в глубину. Впрочем нет, давайте рассмотрим другой пример: нам надо распечатать дерево выражений в форме обратной польской записи. То есть для дерева 1 мы хотим напечатать «2 2 +» а для дерева 2 «2 2 + 2 2 + *».
Запускаем, и ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Лезем в документацию, и обнаруживаем функцию sys.getrecursionlimit . А теперь давайте отойдём от мира интерпретируемых языков, и перейдём в мир языков, которые запускаются прямо на процессоре. Например, на C++.
Запускаем… «Bus error (core dumped)». Судя по gdb, в момент падения стек глубиной 104790 фреймов. А что произойдёт, если мы захотим печатать не просто подряд через пробелы, а выводить еще "{" и "}" вокруг выражений? Ну то есть для дерева 1 чтобы результатом было {2 2 +} а для дерева 2 - {{2 2 +}{2 2 +}*}? Перепишем…Так в чем же проблема?
Использование рекурсивного алгоритма подразумевает использование практически не контролируемого ресурса: стека вызовов
.Что же делать?
Если мы работаем не на микроконтроллере, о объёме стека можно не задумываться: для обычной цепочки вызовов его должно хватать. При условии, разумеется, что мы заботимся гигиене локальных переменных: большие объекты и массивы выделяются используя память (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) так и контекст обработки (в нашем случае - до или после обработки детей). В случаях, когда нужно что-то делать между каждым из рекурсивных вызовов, либо добавляются фазы обработки. Обратите внимание: это уже оптимизированный алгоритм, складывающий всех детей в стек сразу, и именно поэтому складывающий в обратном порядке. Это гарантирует сохранение того же порядка, что и у исходного нерекурсивного алгоритма.
Да, переход на безрекурсивные технологии не совсем бесплатен: мы платим периодически более дорогим - динамическим выделением памяти для организации стека. Впрочем, это окупается: в «ручной стек» сохраняются не вообще все локальные переменные, а только минимально необходимый контекст, размер которого уже можно контролировать. Вторая статья расходов: читабельность кода. Код, записанный в нерекурсивном виде несколько сложнее для восприятия за счет ветвлений от текущего состояния. Решение этой проблемы лежит уже в области организации кода: вынесение шагов в отдельные функции и грамотное их наименование.Злоключение
Несмотря на наличие некоего «налога на обезрекурсивание», я лично считаю его обязательным к уплате в любом месте, где идёт обработка данных, так или иначе поступивших от пользователя.Что такое рекурсия?
Опасности рекурсии
Бесконечная рекурсия
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
Предполагается что читатель теоритически знаком с рекурсией и знает что это такое. В данной статье мы бóльшее вниманиее уделим задачам на рекурсию.Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач. Как же решать задачи на рекурсию?
В первую очередь надо понимать что рекурсия это своего рода перебор. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции.
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Рассмотрим это на примере нахождения факториала :
Добавить метки