Рекурсивные алгоритмы на php. часть 1. основы рекурсии

Частично рекурсивная функция

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

Оператор минимизации аргумента. Пусть f{\displaystyle f} — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции f{\displaystyle f} называется функция h{\displaystyle h} от n−1{\displaystyle n-1} переменной, задаваемая следующим определением:

h(x1,…,xn−1)=miny{\displaystyle h(x_{1},\ldots ,x_{n-1})=\min y}, при условии f(x1,…,xn−1,y)={\displaystyle f(x_{1},\ldots ,x_{n-1},\,y)=0}
То есть функция h{\displaystyle h} возвращает минимальное значение последнего аргумента функции f{\displaystyle f}, при котором её значение равно 0.

Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция f{\displaystyle f} может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и исключение или уход в бесконечный цикл, соответствующие неопределённому значению.

Два способа мышления

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


Рассмотрим два способа её реализации.

  1. Итеративный способ: цикл :

  2. Рекурсивный способ: упрощение задачи и вызов функцией самой себя:

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

Когда функция вызывается, исполнение делится на две ветви:

  1. Если , тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: равно .
  2. Мы можем представить в виде: . Что в математике записывается как: . Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на ) и более простой аналогичной задаче ( с меньшим ). Последующие шаги упрощают задачу всё больше и больше, пока не достигает .

Говорят, что функция рекурсивно вызывает саму себя до .

Например, рекурсивный вариант вычисления состоит из шагов:

Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – к ещё более простому и так далее, пока значение не станет очевидно.

Рекурсивное решение обычно короче

Рекурсивное решение задачи обычно короче, чем итеративное.

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

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

Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.


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

Контрольные примеры

Приведенные ниже контрольные примеры запускались в 64-разрядной среде исполнения IBM Java Runtime Environment (JRE) 7.0.4.0 (с аргументом командной строки -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). Чтобы среда исполнения не тратила время на расширение и сжатие кучи, JRE запускалась с фиксированным размером кучи 256 МБ. Отключение API Attach не позволяет JRE запускать приложения-агенты (обычно используемые для мониторинга), что нормализует производительность в каждом тесте. При увеличении стека вызовов для инициализации стека и поддержания его на уровне 3 МБ использовался аргумент командной строки -Xss3m -Xssi3m.

Вычисление суммы

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

Рисунок 1. Рисунок 1. Вычисление суммы

Вычисление факториала

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

Области применения рекурсии

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

В задаче, получившей название Ханойская башня, даны три стрежня и диски разного размера, которые в исходном состоянии надеты на первый стержень в виде башни. Задача состоит в том, чтобы перенести башню на другой стержень, при этом запрещается класть большой диск на маленький. Эту замечательную задачу можно легко решить с помощью рекурсии за 2n — 1 ходов, где n — число дисков.

Например, возьмем четыре диска и попытаемся перенести их со стержня A на стержень C, используя стержень B для временного хранения. С помощью описанной ниже рекурсивной функции это может быть выполнено за 15 ходов. Процесс решения можно визуализировать этим апплетом. Функция вызывается (2n * 2) – 1, или 31 раз. Причина, по которой число вызовов функции не равно числу ходов, кроется в том, что для обработки ходов необходимо установить стек вызовов. В этом примере используется головная рекурсия (листинг 4).

Листинг 4. Листинг 4
private  static void solveTower(int num, int fromPeg, int toPeg,
			int tempPeg) {
 		if (num > 0) {
 			// move a disc from the fromPeg to the tempPeg
			solveTower(num - 1, fromPeg, tempPeg, toPeg);

 			System.out.println("Disc moved from " + fromPeg + " to " + toPeg);

 			// move disc from the tempPeg to the toPeg
			solveTower(num - 1, tempPeg, toPeg, fromPeg);
		}
	}

Результат для четырех дисков показан в листинге 5.

Листинг 5. Листинг 5
1. Диск перенесен с 1 на 2
2. Диск перенесен с 1 на 3
3. Диск перенесен с 2 на 3
4. Диск перенесен с 1 на 2
5. Диск перенесен с 3 на 1
6. Диск перенесен с 3 на 2
7. Диск перенесен с 1 на 2
8. Диск перенесен с 1 на 3
9. Диск перенесен с 2 на 3
10. Диск перенесен с 2 на 1
11. Диск перенесен с 3 на 1
12. Диск перенесен с 2 на 3
13. Диск перенесен с 1 на 2
14. Диск перенесен с 1 на 3
15. Диск перенесен с 2 на 3

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

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

Листинг 6. Листинг 6
int  numMoves = (1 << numDiscs) - 1;
int [] pegs = { 1, 2, 3, 1, 3, 2 };
int  count = 0;
		
for  (int currMove=1; currMove <= numMoves; currMove++) {
	int disc = 0;
 	while ( (currMove >> disc & 1) == 0 ) {  
		disc++;
	}
 	int level=(numDiscs - disc) & 1;  
 	int fromPeg =(currMove >> ++disc) % 3;
	fromPeg = pegs;
 	int toPeg =(fromPeg + level) % 3 + 1 ;
 	System.out.println (++count + ". Disc moved from " + fromPeg  + " to " + toPeg) ;
}

Рекурсия или итерирование

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

Итерационная процедура Рекурсивная процедура

123456789101112131415

#include <iostream>using namespace std;int fact(int num) {   int rez = 1;   for (int i = 1; i <= num; i++)   rez *= i;   return rez; }int main() {   cout << fact(3);   cin.get();   return 0; }

123456789101112131415

#include <iostream>using namespace std;int fact(int num) {   if(num==1) return 1;   return num*fact(num — 1); }int main() {   cout << fact(3);   cin.get();   return 0; }

Вызов функции влечет за собой некоторые дополнительные накладные расходы, связанные с передачей управления и аргументов в функцию, а также возвратом вычисленного значения. Поэтому итерационная процедура вычисления факториала будет несколько более быстрым решением. Чаще всего итерационные решения работают быстрее рекурсивных.Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами.Еще одним недостатком рекурсии является то, что ей может не хватать для работы стека. При каждом рекурсивном вызове в стеке сохраняется адрес возврата и передаваемые аргументы. Если рекурсивных вызовов слишком много, отведенный объем стека может быть превышен. (Например, рекурсивное вычисление факториала отрицательного числа).Однако процедуры, вызывающие себя два и более раз чаще всего не имеют простого нерекурсивного аналога. В этом случае множество вызываемых процедур образует не цепочку, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения. Кроме того, рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные.

Алгоритмизация

В культуре

См. также: Mise en abyme и Эффект Дросте

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

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Тема рекурсии присутствует во многих рассказах и очерках аргентинского писателя Хорхе Луиса Борхеса.

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

рассказ про Ийона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

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

  • Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
  • Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), WINE (Wine Is Not an Emulator) и т. д.
  • Герб Российской Федерации является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия.
  • Рассказ Генри Каттнера «Порочный круг».
  • Стихотворение детского поэта Андрея Усачева «Жучок»
  • Стихотворение М. Ю. Лермонтова «Сон»
  • Поисковая система Google при запросе «рекурсия» выводит надпись «Возможно, вы имели в виду: рекурсия»

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

Другим отличным применением рекурсии является рекурсивный обход.


Представьте, у нас есть компания. Структура персонала может быть представлена как объект:

Другими словами, в компании есть отделы.

  • Отдел может состоять из массива работников. Например, в отделе работают 2 сотрудника: Джон и Алиса.

  • Или отдел может быть разделён на подотделы, например, отдел состоит из подотделов: и . В каждом подотделе есть свой персонал.

  • Также возможно, что при росте подотдела он делится на подразделения (или команды).

    Например, подотдел в будущем может быть разделён на команды и . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.

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

Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл поверх объекта с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.

Давайте попробуем рекурсию.

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

  1. Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
  2. Или это объект с подотделами – тогда мы можем сделать рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.

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

Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).


Алгоритм даже проще читается в виде кода:

Код краток и прост для понимания (надеюсь?). В этом сила рекурсии. Она работает на любом уровне вложенности отделов.

Схема вызовов:

Принцип прост: для объекта используются рекурсивные вызовы, а массивы являются «листьями» дерева рекурсии, они сразу дают результат.

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

  • Метод из главы Методы массивов для получения суммы элементов массива.
  • Цикл для итерации по значениям объекта: возвращает массив значений.

Хвостовая рекурсия и цикл

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

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

Для реализации такого поведения используется стек (стек вызовов, 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)
конец

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

Бесконечно

Возможно, аноним пытается сказать, что в рамках ограниченного количества доступной оперативной памяти, о бесконечности в программировании речи идти не может. Может, как-то поправить на «потенциально бесконечное» или как-то так? —Illythr (Толк?) 14:42, 30 августа 2009 (UTC)

Рекурсия — она бывает не только в программах для компьютеров с конечным объемом памяти. В математике и computer science есть понятие рекурсивного типа данных — где рекурсия используется для задания бесконечного множества объектов. Множества всех возможных двоичных деревьев, например. — X7q 14:53, 30 августа 2009 (UTC)
Верно, но раздел называется «Рекурсия в программировании». 🙂 Может, просто приписать «теоретически»? —Illythr (Толк?) 14:58, 30 августа 2009 (UTC)
Да, я тоже думаю с «теоретически» было бы правильнее. — X7q 07:14, 31 августа 2009 (UTC)
«Бесконечную» рекурсию можно организовать и с конечным стеком, было бы желание. 91.207.100.2 07:41, 16 июня 2011 (UTC)

Литература

  1. Многопоточный сервер Qt. Пул потоков. Паттерн Decorator – режим доступа: https://pro-prof.com/archives/1390. Дата обращения: 21.02.2015.
  2. Джейсон Мак-Колм Смит Элементарные шаблоны проектирования : Пер. с англ. — М. : ООО “И.Д. Вильямс”, 2013. — 304 с.
  3. Скиена С. Алгоритмы. Руководство по разработке.-2-е изд.: пер. с англ.-СПб.:БХВ-Петербург, 2011.-720с.: ил.
  4. Васильев В. С. Анализ сложности алгоритмов. Примеры – режим доступа: https://pro-prof.com/archives/1660. Дата обращения: 21.02.2015.
  5.  А.Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы, М., Вильямс, 2007.
  6. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. — М. : БИНОМ. Лаборатория знаний, 2006. — 406 с.
  7. Сергиевский Г.М. Функциональное и логическое программирование : учеб. пособие для студентов высш. учеб. заведений / Г.М. Сергиевский, Н.Г. Волченков. — М.: Издательский центр «Академия», 2010.- 320с.
  8. Книги по алгоритмам и структурам данных: – режим доступа: https://pro-prof.com/books-algorithms. Дата обращения: 21.02.2020.

В математике

См. также: Рекурсивная функция

Треугольник Серпинского

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

  • Конечная рекурсивная функция. Она задаётся таким образом, чтобы для любого конечного аргумента за конечное число рекурсивных обращений привести к одному из отдельно определённых частных случаев, вычисляемых без рекурсии. Классический пример: рекурсивно-определённый факториал целого неотрицательного числа: n!={n⋅(n−1)!,n>1,n={\displaystyle n!={\begin{cases}n\cdot (n-1)!,&n>0\\1,&n=0\end{cases}}}. Здесь каждое следующее рекурсивное обращение делается с аргументом, меньшим на единицу. Поскольку n, по определению, целое неотрицательное число, через n рекурсивных обращений вычисление функции гарантированно придёт к частному случаю !=1{\displaystyle 0!=1}, на котором рекурсия прекратится. Таким образом, несмотря на рекурсивность определения, вычисление функции для любого аргумента из области определения окажется конечным.
  • Бесконечная рекурсивная функция. Она задаётся в виде обращения к самой себе во всех случаях (по крайней мере, для некоторых из аргументов). Подобным образом могут задаваться бесконечные ряды, бесконечные непрерывные дроби и так далее. Практическое вычисление точного значения здесь, естественно, невозможно, поскольку потребует бесконечного времени. Требуемый результат находится аналитическими методами. Тем не менее, если речь идёт не о получении абсолютно точного значения, а о вычислении заданного приближения искомого значения, то тут в некоторых случаях возможно прямое использование рекурсивного определения: вычисления по нему ведутся до тех пор, пока необходимая точность не будет достигнута. Примером может служить разложение в непрерывную дробь числа e:
e=2+22+33+44+…=2+f(2){\displaystyle e=2+{\cfrac {2}{2+{\cfrac {3}{3+{\cfrac {4}{4+\ldots }}}}}}\;=2+f(2)}, где f(n)=nn+f(n+1){\displaystyle f(n)={\cfrac {n}{n+f(n+1)}}}
Прямой расчёт по приведённой формуле вызовет бесконечную рекурсию, но можно доказать, что значение f(n) при возрастании n стремится к единице (поэтому, несмотря на бесконечность ряда, значение числа Эйлера конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо f(n){\displaystyle f(n)} единицу.

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

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

В математике отдельно рассматривается класс так называемых «примитивно рекурсивных» функций. Определение примитивно рекурсивной функции также рекурсивно, оно задаёт набор примитивных функций и набор правил; функция является примитивно рекурсивной, если она может быть представлена как комбинация примитивно рекурсивных функций, образованная по этим правилам.

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

  • Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.
  • Уже упоминавшийся факториал целого неотрицательного числа.
  • Числа Фибоначчи определяются с помощью рекуррентного соотношения:
    Первое и второе числа Фибоначчи равны 1
    Для n>2{\displaystyle n>2}, n{\displaystyle n}-e число Фибоначчи равно сумме (n−1){\displaystyle (n-1)}-го и (n−2){\displaystyle (n-2)}-го чисел Фибоначчи
  • Практически все геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского).
  • Стандартный пример вычислимой рекурсивной функции, не являющейся примитивно рекурсивной — функция Аккермана: для неотрицательных целых чисел m{\displaystyle m} и n{\displaystyle n} следующим образом:
A(m,n)={n+1,m=;A(m−1,1),m>,n=;A(m−1,A(m,n−1)),m>,n>{\displaystyle A(m,\;n)={\begin{cases}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m-1,\;A(m,\;n-1)),&m>0,\;n>0.\end{cases}}}

С этим читают