Зачем ходить по кругу, или Что отражают тысячи зеркал

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

Сложно? Давайте разбираться на простых примерах. С набором матрешек вроде бы все понятно: их несколько, они похожи друг на друга, только разного размера. Поэтому один объект «матрешка» может помещаться в другой, больший по размеру объект «матрешка». На гербе России изображен двуглавый орел со скипетром и державой. На скипетре снова представлен двуглавый орел, то есть один объект находится внутри другого объекта.

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

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

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

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

В литературе тоже можно найти характерный пример рекурсии. Во-первых, в народной песенке-прибаутке: «У попа была собака, он ее любил. / Она съела кусок мяса, он ее убил. / В землю закопал и надпись написал: «У попа была собака, он ее любил…»

А один из ярких примеров рекурсивного романа — «Мастер и Маргарита». Здесь развивается одна алгоритмическая схема: Мастер и Маргарита, Иешуа и Пилат, Воланд и компания. Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь используется прием «книга в книге». Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги «Мастер и Маргарита».

— Понятие «рекурсия» метапредметно, поэтому оно присутствует в разных областях нашей жизни, — объясняет учитель информатики гимназии № 1517 Екатерина Волкова. — Главное в ее алгоритме — разбить любую задачу на простые шаги. А потом каждый из них еще раз разложить на более меткие и так далее, пока мы не придем к самым элементарным «шажочкам».