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

Примеры[править | править код]

• Алгоритм Жордана-Гаусса для решения СЛАУ является рекурсивным.
• Факториал целого неотрицательного числа n обозначается n! и определяется как

  n!=n×(n-1)! при n>0 и n!=1 при n=0

• Числа Фибоначчи определяются с помощью рекурсии:

  Первое и второе числа Фибоначчи равны 1

  Для n>2, n-е число Фибоначчи равно сумме (n-1)-го и (n-2)-го чисел Фибоначчи

• Практически все геометрические фракталы задаются в форме бесконечной рекурсии. (например, триадическая кривая Коха).
• Задача «Ханойские башни». Её содержательная постановка такова:

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

  Рекурсивный вариант решения задачи :

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

В языке программирования ActionScript рекурсия выглядит следующим образом:

В данном примере показан в виде рекурсионной функции поиск объекта с конкретно описанными свойствами (в строке 4) внутри бесконечно глубокого дерева объектов.

Или вот так:

Устранение непосредственной левой рекурсии[править]

Опишем процедуру, устраняющую все правила вида , для фиксированного нетерминала .

1. Запишем все правила вывода из в виде:
   , где
   • — непустая последовательность терминалов и нетерминалов ();
   • — непустая последовательность терминалов и нетерминалов, не начинающаяся с .
2. Заменим правила вывода из на .
3. Создадим новый нетерминал .

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

Примерправить

Есть непосредственная левая рекурсия . Добавим нетерминал и добавим правила , .

Новая грамматика:

В новой грамматике нет непосредственной левой рекурсии, но нетерминал леворекурсивен, так как есть

Рекурсивные структуры

Рекурсивная (рекурсивно определяемая) структура данных – это структура, которая повторяет саму себя в своих частях.

Мы только что видели это на примере структуры компании выше.

Отдел компании – это:

• Либо массив людей.
• Либо объект с отделами.

Для веб-разработчиков существуют гораздо более известные примеры: HTML- и XML-документы.

В HTML-документе HTML-тег может содержать:

• Фрагменты текста.
• HTML-комментарии.
• Другие HTML-теги (которые, в свою очередь, могут содержать фрагменты текста/комментарии или другие теги и т.д.).

Это снова рекурсивное определение.

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

Представьте себе, что мы хотим хранить упорядоченный список объектов.

Естественным выбором будет массив:

…Но у массивов есть недостатки. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция должна переиндексировать все элементы, чтобы освободить место для нового , и, если массив большой, на это потребуется время. То же самое с .

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

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

Элемент связанного списка определяется рекурсивно как объект с:

• ,
• – свойство, ссылающееся на следующий элемент связанного списка или , если это последний элемент.

Пример:

Графическое представление списка:

Альтернативный код для создания:

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

Список можно легко разделить на несколько частей и впоследствии объединить обратно:

Для объединения:

И, конечно, мы можем вставить или удалить элементы из любого места.

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

Чтобы удалить элемент из середины списка, нужно изменить значение предыдущего элемента:

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

В отличие от массивов, нет перенумерации, элементы легко переставляются.

Естественно, списки не всегда лучше массивов. В противном случае все пользовались бы только списками.

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

…Но нам не всегда нужны такие операции. Например, нам может быть нужна очередь или даже двухсторонняя очередь – это упорядоченная структура, которая позволяет очень быстро добавлять/удалять элементы с обоих концов, но там не нужен доступ в середину.

Списки могут быть улучшены:

• Можно добавить свойство в дополнение к для ссылки на предыдущий элемент, чтобы легко двигаться по списку назад.
• Можно также добавить переменную , которая будет ссылаться на последний элемент списка (и обновлять её при добавлении/удалении элементов с конца).
• …Возможны другие изменения: главное, чтобы структура данных соответствовала нашим задачам с точки зрения производительности и удобства.

Плюсы:

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

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

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

Рекурсию легче отлаживать.

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

Рекурсию можно увидеть

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

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

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

Капуста романеско. Фото: Reissaamme / Pixabay.com

В архитектуре рекурсия встречается в облике готических соборов.

Реймсский собор. Фото: Ruben Holthuijsen / Flickr.com

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

А вот рекурсивная версия того же узора — Собор Линкольна.

Собор Линкольна. Фото: Dom Crossley / Flickr.com

Здесь окно тоже выполнено в форме остроконечной арки с вписанным в неё кругом, а круг лежит на двух других арках. Вот только внутри каждой из этих арок — снова круг и две ещё меньших арки, а внутри них — ещё по одному кругу на двух меньших арках.

Другой пример архитектурной рекурсии — собор Святого Петра в Ватикане.

Собор Святого Петра. Фото: Mike McBey / Flickr.com

Джордж Херси, американский писатель и журналист, его с китайскими шкатулками с секретом. По его словам, архитектурный комплекс состоит из одной макроцеркви, четырёх наборов того, что журналист назвал макси-церквями, 16 мини-церквей и 32 микроцерквей. А мог бы просто сказать, что собор рекурсивный.

В изобразительном искусстве рекурсия тоже отметилась — взять хотя бы «Триптих Стефанески» Джотто. На его центральной панели изображён кардинал Стефанески, которой держит в руках этот же триптих (на котором тоже изображён триптих и так далее).

«Триптих Стефанески», Джотто. Оборотная сторона. Фото:

А вот пример посвежее — литография «Рисующие руки» нидерландского художника XX века Маурица Эшера:

Литография «Рисующие руки», Мауриц Корнелис Эшер. Фото: Renzo Giusti / Flickr.com

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

Переходим к общим случаям

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

Большой случай?

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

reverse(string) = reverse(string) + reverse(string)

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

Применив это решение к функции , мы получаем следующее:

reverse(string):  if len(string) == 0:    return ''  else:    return string + reverse(string)

Визуализации рекурсивной функции reverse

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

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

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

Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.

Рекурсия в программировании[править | править код]

В программировании рекурсия — вызов функции или процедуры из неё же самой (обычно с другими значениями входных параметров), непосредственно или через другие функции (например, функция А вызывает функцию B, а функция B — функцию A). Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

Вырожденный вариант — для случая, когда из каждого узла выходит строго одна ветка — известен как «хвостовая рекурсия». Она эквивалентна циклу, служащему, как известно, средством обхода линейной последовательности. Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций.

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

<?php

// Пример бесконечной рекурсии

function foo(){
return foo();
}

foo();

?>

1 2 3 4 5 6 7 8 9 10 11

<?php   // Пример бесконечной рекурсии   functionfoo(){ returnfoo(); }   foo();   ?>

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

То же самое касается и примера со сложной рекурсией.

<?php

// Пример сложной бесконечной рекурсии

function foo(){
return bar();
}

function bar(){
return foo();
}

foo();

?>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

<?php   // Пример сложной бесконечной рекурсии   functionfoo(){ returnbar(); }   functionbar(){ returnfoo(); }   foo();   ?>

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

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

<?php

// Пример конечной рекурсии

function foo($n){
if($n < 1)
return;
return foo($n-1);
}

foo(100000);

?>

1 2 3 4 5 6 7 8 9 10 11 12 13

<?php   // Пример конечной рекурсии   functionfoo($n){ if($n<1) return; returnfoo($n-1); }   foo(100000);   ?>

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

Примитивно рекурсивные множества

Будем называть множество примитивно рекурсивным, если его
характеристическая функция примитивно рекурсивна. (Вариант: если
оно является множеством нулей примитивно рекурсивной функции;
это то же самое, так как можно сделать подстановку в
функцию .)

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

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

Функция , заданная соотношением

 f(x) = ,

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

Теперь можно записать формулу для прибавления единицы по
модулю (для чисел, меньших ):

 x+1 mod n = 

После этого функцию (остаток от деления на ) можно определить рекурсивно:

 0 mod n = 0;
 (x+1) mod n = (x mod n) + 1 mod n.

Покажем, что ограниченные кванторы, примененные к примитивно рекурсивным свойствам (множествам), дают снова примитивно рекурсивные
свойства. Это означает, например, что если свойство
примитивно рекурсивно, то свойства

 S(x,z)=(∃ y ≤ z) R(x,y)

и

 T(y,z)=(∀ y ≤ z) R(x,y)

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

А произведение легко определить рекурсивно:

с суммированием можно поступить аналогичным образом.

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

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

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

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

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

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

Персональные компьютеры сегодня

• Ученые Массачусетского технологического института работают над тем, чтобы устранить из персональных компьютеров провода. Это приспособление для передачи информации устарело и требует апгрейда — отличной заменой традиционным проводам станут импульсы германиевых лазеров, которые уже внедряют в компьютер.
• Интересным направлением развития современного ПК можно считать внедрение в него различных умных гаджетов. Умные часы, сенсоры сердцебиения, датчики осанки – все это мы видели вне персонального компьютера, теперь же ведутся работы по внедрению в него этих полезных для здоровья находок.
• В компьютер планируется внедрить новую технологию хранения данных – мемристорную память. Благодаря уникальным чипам из диоксида титана и платины компьютер сможет обрабатывать данные в 1 000 раз быстрее, совершать миллионы циклов перезаписи и моментально обрабатывать сведенья.
• Для современных компьютеров длительное хранение энергии также является проблемой, поэтому ведутся активные разработки в направлении инновационных батарей для компьютера, которые позволят заряжать и разряжать аккумулятор много тысяч раз.
• Последние разработки компьютеров и вовсе кажутся пугающими – нам предлагают совместить электронно-вычислительную машину с человеческим мозгом! Такая киборгизация компьютера предполагает присоединение своеобразной полимерной сетки с электродами к специальным имплантам-нейронам в мозге человека. Предполагается большой арсенал функций компьютера: от лечения болезни Альцгеймера и Паркинсона до управления сложными конструкциями силой мысли.

Тарас С.Частный инвестор, предприниматель, блогер. Инвестирую с 2008 года. Зарабатываю в интернете на высокодоходных проектах, криптовалютах, IPO, акциях и других активах. Со-владелец нескольких ресторанов и сети магазинов электронной техники. Консультирую партнеров, делюсь опытом. Присоединяйся в Telegram-канал блога со свежими новостями.

Чат с консультантом в Телеграм.

История создания и развития компьютеров

Первое поколение ЭВМ: ламповые компьютеры

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

Один из первых ламповых компьютеров – ENIAC

Появление транзисторов и второе поколение ЭВМ

транзистора

• Габариты такого компьютера значительно уменьшились.
• Увеличилась производительность – от сотен тысяч до 1 млн. операций в секунду.
• Память компьютера составляла несколько десятков тысяч слов, оперативка достигала до 32 Кбайт.
• Благодаря транзисторному компьютеру начинается развитие языков программирования высокого уровня.

США
Полезное чтение:

• История создания Интернета
• История часов: как возникли первые в мире часы?
• История телефонов: как появился первый телефон?
• История биткоина (Bitcoin) кратко

Третье поколение ЭВМ: первые стандарты

• Компьютер значительно уменьшился в размере – его можно было с легкостью поставить на стол.
• Производительность увеличена до миллионов операций в секунду.
• За счет создания микросхем гораздо упростилась не только эксплуатация компьютера, но и его ремонт.
• Машины третьего поколения были программно-совместимыми между собой, так как имели общую архитектуру.
• Компьютер мог выполнять несколько задач одновременно.
• В качестве внешних запоминающих устройств используются магнитные диски, которые работают гораздо быстрее своих предшественниц — магнитных лент.

IBM
Компьютер класса «мейнфрейм» – IBM System/360

Intel

Первые персональные компьютеры

Стивен ДжобсApple Computer
Один из первых серийных компьютеров – Apple II

Факториал

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

function factorial($n) 
{
 if ($n <= 1) return 1; 
 return $n * factorial($n - 1); // здесь происходит повторный вызов функции 
} 

echo factorial(5); // 120

Факториал числа так же можно вычислить, применив цикл, полностью заменяющий рекурсию:

function factorial($n) 
{
 $result = 1; 
 for ($i = 1; $i <= $n; $i++) { 
  $result *= $i; 
 } 
 return $result; 
} 

echo factorial(5); // 120 

Класс дерева категорий

CREATE TABLE IF NOT EXISTS category (
 `id` INT NOT NULL AUTO_INCREMENT,
 `name` VARCHAR(100) NOT NULL,
 `parent_id` VARCHAR(40) NOT NULL,   
 PRIMARY KEY ( id )
) ENGINE=InnoDB DEFAULT CHARSET=utf-8 COLLATE=utf8mb4_unicode_ci;

INSERT INTO category (`id`, `name`, `parent_id`) VALUES
(1, 'Компьютеры и периферия', 0),
(2, 'Комплектующие для ПК', 0),
(3, 'Смартфоны и смарт-часы', 0),
(4, 'Телевизоры и медиа', 0),
(5, 'Игры и приставки', 0),
(6, 'Аудиотехника', 0),
(7, 'Фото-видеоаппаратура', 0),
(8, 'Офисная техника и мебель', 0),
(9, 'Компьютерные системы', 1),
(10, 'Периферия', 1),
(11, 'Программное обеспечение и аксессуары', 1),
(12, 'Системные блоки', 9),
(13, 'Моноблоки', 9),
(14, 'Неттопы и компьютеры-флешки', 9),
(15, 'Платформы', 9),
(16, 'Игровые компьютеры', 12),
(17, 'Компьютеры для офиса', 12),
(18, 'Компьютеры для бизнеса', 12),
(19, 'Сенсорные моноблоки', 13),
(20, 'Моноблоки с IPS экраном', 13),
(21, 'Моноблоки с VA экраном', 13),
(22, 'Моноблоки с TN экраном', 13),
(23, 'Основные комплектующие', 2),
(24, 'Хранение данных и охлаждение', 2);

Класс :

<?php
require 'DB.php';

class Category
{
  /**
   * @return array
   * Получаем все категории
   */
  public function getData()
  {
    $db = new DB();
    return $db::getRows("SELECT * FROM `category`");
  }

  /**
   * @param $data
   * @return mixed
   * Строим дерево
   */
  public function createTree($data)
  {
    $parents = [];
    foreach ($data as $key => $item):
      $parents = $item;
    endforeach;
    $treeElem = $parents;
    $this->generateElemTree($treeElem, $parents);
    return $treeElem;
  }

  /**
   * @param $treeElem
   * @param $parents
   * Генерируем элементы дерева с учётом удобного вывода потомков
   */
  private function generateElemTree(&$treeElem, $parents)
  {
    foreach ($treeElem as $key => $item):
      if (!isset($item->children)):
        $treeElem->children = [];
      endif;

      if (array_key_exists($key, $parents)):
        $treeElem->children = $parents;
        $this->generateElemTree($treeElem->children, $parents);
      endif;
    endforeach;
  }

  /**
  * @param $data
  * Рендерим вид
  */
  public function renderTemplate($data) {
  echo "<ul>";
  if(is_array($data)):
   foreach ($data as $item):
    echo '<li>';
    echo "<a href=\"/?=/{$item->id}\">";
    echo $item->name;
    echo "</a>";
    if(count($item->children) > 0):
     $this->renderTemplate($item->children);
    endif;
    echo '</li>';
   endforeach;
  endif;
  echo "</ul>";
 }
}

Выводим дерево категорий:

require 'Category.php';

$category = new Category();
$data = $category->getData();
$tree = $category->createTree($data);
$category->renderTemplate($tree);

Другие виды рекурсии

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

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

Совместная рекурсия. Пусть две одноместные функции и заданы соотношениями:

 f(0) = a,
 g(0) = b,
 f(n+1) = F(n,f(n),g(n)),
 g(n+1) = G(n,f(n),g(n)),

где и некоторые числа, а
функции и примитивно
рекурсивные функции трех аргументов. Покажем, что тогда функции
и примитивно рекурсивны.

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

 h(0) = ,
 h(n+1) = [F(n,p1(h(n)),p2(h(n))),G(n,p1(h(n)),p2(h(n)))],

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

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

  6
  3  7 
  1  4  8 
  0  2  5  9

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

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

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

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

Теорема 74. Пусть функция
одного аргумента примитивно рекурсивна, причем
при ; пусть примитивно рекурсивная функция
двух
аргументов; пусть произвольная константа. Тогда
функция , определенная соотношениями

 h(0) = c,
 h(x) = F(x,h(g(x))) при x>0
 

примитивно рекурсивна.

Чтобы доказать эту теорему, используем следующую нумерацию конечных последовательностей натуральных чисел: номером пустой
последовательности считаем число , номером одноэлементной
последовательности считаем
число ,
последовательность имеет
номер , последовательность
имеет номер и так далее (основания
степеней простые числа). Будем обозначать номер
последовательности
через . Эта нумерация в некотором смысле примитивно
рекурсивна. Конечно, буквально это понимать нельзя, так как
нумерация представляет собой » функцию с переменным числом
аргументов». Но разные связанные с ней функции примитивно
рекурсивны. В частности, таковы функции

• длина последовательности с номером ;
• -ый член последовательности с номером ;
• номер последовательности, которая получается приписыванием числа к последовательности с номером .

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

Теперь мы докажем, что функция

примитивно рекурсивна. В самом деле, , а

 H(k+1)= Append(H(k),F(k+1,Select(g(k+1),H(k)))).

Дом, который построил Джек

Чтобы было понятнее, что такое рекурсия, возьмём стихотворение Самуила Маршака «Дом, который построил Джек»:

Вот дом,
Который построил Джек.

А это пшеница,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

А это весёлая птица-синица,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

Вот кот,
Который пугает и ловит синицу,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

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

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

Нулевой уровень:

Вот дом,
Который построил Джек.

Обозначим его за и дальше будем увеличивать это число для каждого уровня. Следите за уровнями.

Первый уровень:

А это пшеница,
Которая в тёмном чулане хранится

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

А это пшеница,
Которая в тёмном чулане хранитсяВ доме,Который построил Джек.

Второй уровень:

А это весёлая птица-синица,
Которая часто ворует пшеницу,

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

А это весёлая птица-синица,
Которая часто ворует пшеницу,Которая в тёмном чулане хранится

А на втором у нас уже появится полноценный стих:

А это весёлая птица-синица,
Которая часто ворует пшеницу,Которая в тёмном чулане хранитсяВ доме,Который построил Джек.

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

Юмор[править | править код]

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

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

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

Русская народная сказка-песня «У попа была собака…» являет пример рекурсии: