Рекурсии — это что? рекурсия в программировании (примеры)

В культуре

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

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

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

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

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

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

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

Примечания

Особенности рекурсии

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

Ино­гда про­грам­мист увле­ка­ет­ся рекур­си­ей и забы­ва­ет про­пи­сать выход из неё. В резуль­та­те рекур­сия бес­ко­неч­но углуб­ля­ет­ся саму в себя, заби­ра­ет в себя все ресур­сы и про­грам­ма пада­ет. Гово­рят, что так обра­зу­ют­ся чёр­ные дыры, в кото­рых всё исче­за­ет.

Быва­ют момен­ты, когда рекур­сия — это един­ствен­ный спо­соб выпол­нить нуж­ную зада­чу. Напри­мер, при пар­син­ге HTML-кода или для постро­е­ния дере­ва зави­си­мо­стей.

В информатике

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

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

unsigned int factorial(unsigned int n) {
    if (n == ) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

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

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

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

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

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

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

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

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;
}

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

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

В искусстве

Рекурсивные куклы: оригинальный набор матрешки по Zvyozdochkin и Малютин , 1892 г.

Передняя поверхность Giotto «s Stefaneschi Триптих , 1320, рекурсивно содержит образ себя (держится на коленах фигуры в центральной панели).

Русская кукла или матрешка — физический художественный пример рекурсивной концепции.

Рекурсия используется в картинах , так как Джотто «s Stefaneschi триптих , выполненный в 1320 году его центральная панель содержит коленопреклоненного фигура кардинала Stefaneschi, подняв саму триптих в качестве подношения.

Эшер «S печати Галерея (1956) является печать на которой изображен искаженный город , содержащий галерею , которая рекурсивно содержит изображение, и так до бесконечности .

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

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

Функции

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

Для работы в отлаженной программе рекурсивная функция должна возвращать значение за конечное время. Это осуществляется через задание «базового» случая, когда для определенного значения аргумента выполняется базовое условие: конечная подпрограмма, свободная от самовызова. Рекурсивные же вызовы должны при этом сходиться за конечное время к базовым случаям. Для информатики особый интерес представляют те рекурсивные функции, полнота которых для всех возможных вводных значений (домена функции) — подвергается математическому доказательству.

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

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

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

Данные

Описание типа данных может содержать самоотсылку. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

class element_of_list; /* необходимо по правилам C++ */
class element_of_list
{
  element_of_list *next; /* ссылка на следующий элемент того же типа */
  int data; /* некие данные */
};

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

Напутствие

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

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

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

Рекурсии - это что? рекурсия в программировании (примеры)

На этом всё, спасибо за внимание. Перевод статьи Tom Grigg: Recursive Programming

Перевод статьи Tom Grigg: Recursive Programming

Рекурсия в программировании

Допу­стим, нам нуж­но посчи­тать сум­му всех чисел от 1 до какого-то чис­ла. Мож­но это сде­лать в цик­ле, а мож­но сде­лать уни­вер­саль­ную функ­цию с рекур­си­ей. Ей будет доста­точ­но ука­зать на вхо­де чис­ло, до кото­ро­го нуж­но всё посчи­тать, а она сама сде­ла­ет всё осталь­ное.

Сна­ча­ла запи­шем это на JavaScript, а потом раз­бе­рём­ся с тем, как рабо­та­ет эта магия:

Пер­вая строч­ка — объ­яв­ле­ние функ­ции function rec(x). Здесь всё как обыч­но — ука­зы­ва­ем назва­ние и гово­рим, что на вход будет посту­пать какая-то пере­мен­ная, с кото­рой мож­но рабо­тать.

Затем мы орга­ни­зу­ем нуле­вой уро­вень — тот, где рекур­сия начи­на­ет­ся: if (x == 1) {return(1)}. Он гово­рит нам: если на вход посту­пит еди­ни­ца, то воз­вра­ща­ем еди­ни­цу. Это логич­но — сум­ма всех чисел от 1 до 1 рав­на еди­ни­це. Это как дом, кото­рый постро­ил Джек — всё в ито­ге све­дёт­ся к это­му.

А даль­ше идёт самое инте­рес­ное — если мы не дошли до еди­ни­цы, то мы берём зна­че­ние x и скла­ды­ва­ем его с резуль­та­том этой же функ­ции, но от преды­ду­ще­го зна­че­ния. Если мы, напри­мер, счи­та­ем rec(10), то эта коман­да сде­ла­ет так:

  1. Про­ве­рит, дошли ли до еди­ни­цы.
  2. Если не дошли — сло­жит 10 и зна­че­ние rec(9).
  3. Для это­го она про­ве­рит, дошли ли до еди­ни­цы.
  4. Если не дошли — сло­жит 9 и зна­че­ние rec(8).
  5. Для это­го она про­ве­рит…
  6. Ура, мы дошли до еди­ни­цы и воз­вра­ща­ем еди­ни­цу обрат­но.
  7. К это­му момен­ту рекур­сия уже дошла до коман­ды 2 + rec(1). Она полу­ча­ет в ответ еди­ни­цу, скла­ды­ва­ет 2 и 1 и воз­вра­ща­ет резуль­тат на уро­вень выше.
  8. На уровне выше была коман­да 3 + rec(2). Она полу­ча­ет в ответ 3, скла­ды­ва­ет 3 и 3 и воз­вра­ща­ет резуль­тат на уро­вень выше.
  9. На послед­нем уровне была коман­да 10 + rec(9). Она полу­ча­ет от преды­ду­ще­го уров­ня резуль­тат 45, скла­ды­ва­ет 10 и 45 и полу­ча­ет резуль­тат 55.
  10. Ура, рекур­сия закон­чи­лась.

Попро­буй­те сами вста­вить код в кон­соль и посмот­ри­те на резуль­тат.

Что подразумевают под рекурсией в программировании?

Рекурсии - это что? рекурсия в программировании (примеры)

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

Возможна также организация сложной рекурсии с помощью двух функций. Допустим, есть А и Б. Функция А имеет в своем коде вызов Б, а Б, в свою очередь, указывает компьютеру на необходимость выполнить А. Сложные рекурсии – это выход из целого ряда сложных логических ситуаций для компьютерной логики.

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

Литература

  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}}}

Вычисление сложного процента рекурсией и циклом FOR

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

  1. Срок кредита в годах
  2. Процентная ставка
  3. Количество платежей в год
  4. Сумма кредита

Формула расчёта сложного процента:

Рекурсии - это что? рекурсия в программировании (примеры)

Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (nt) будет обрабатываться в итерациях.

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

Расчёт по сложной процентной ставке итеративно

Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.

Так выглядит код:

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

Результат наших вычислений:

Расчёт по сложной процентной ставке рекурсивным способом

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

Условие 1: Счётчик не равен 0.

Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.

Условие 2: Счётчик равен 0

Возврат общей суммы

В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.

Здесь происходит тоже самое, только начальное значение теперь 120

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

Суть рекурсии

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

Рекурсии - это что? рекурсия в программировании (примеры)
Мы каждый раз разделяем задачу «P» на шаги и оставшуюся упрощённую задачу той же формы, что и оригинал, пока не достигнем простого решения небольшой проблемы (базовый случай).

Предположим, у нас есть фактические данные определённого типа, назовём их dₒ. Идея рекурсии состоит в том, чтобы предположить, что мы уже решили задачу или вычислили желаемую функцию f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.

В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).

Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:

fib(n):  if n == 0:    return 0  if n == 1:    return 1  else:    return fib(n-1) + fib(n-2)

Как будет выглядеть выполнение такой функции? Возьмём для примера :

Визуализация древа рекурсии, показывающая рекурсивное вычисление, которое приводит к fib(4) = 3

Обратите внимание, что вычисление сначала выполняется в глубину

В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи. Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения мы действуем, как будто мы уже рассчитали и В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем и , которые имеют фиксированные и простые решения.

Рекурсии - это что? рекурсия в программировании (примеры)
«Притворяйся, пока это не станет правдой»

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

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

  1. Упорядочить данные
  2. Решить малую часть проблемы
  3. Решить большую часть проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры рекурсивных алгоритмов

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

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

Поиск элемента массива

начало; 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 < Array2
    результат := Array1
    i := i + 1
  иначе (если Array1 >= Array2)
    результат := Array2
    j := j + 1
конец; вернуть результат