Рекурсивный расизм. Рекуррентные соотношения

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

1. Сущность рекурсии

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

Пример рекурсивной процедуры:

Procedure Rec(a: integer); begin if a>

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

Рис. 1. Блок схема работы рекурсивной процедуры.

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии .

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рис. 2.

Рис. 2. Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

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

Procedure Rec2(a: integer); begin writeln(a); if a>0 then Rec2(a-1); end;

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

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

Procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры} procedure B(n: integer); {Опережающее описание второй процедуры} procedure A(n: integer); {Полное описание процедуры A} begin writeln(n); B(n-1); end; procedure B(n: integer); {Полное описание процедуры B} begin writeln(n); if n

Опережающее описание процедуры B позволяет вызывать ее из процедуры A. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.

Если обычную рекурсию можно уподобить уроборосу (рис. 3), то образ сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию.

Рис. 3. Уроборос – змей, пожирающий свой хвост. Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

Рис. 4. Сложная рекурсия.

3. Имитация работы цикла с помощью рекурсии

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

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

Пример 1.

Procedure LoopImitation(i, n: integer); {Первый параметр – счетчик шагов, второй параметр – общее количество шагов} begin writeln("Hello N ", i); //Здесь любые инструкции, которые будут повторятся if i

Результатом вызова вида LoopImitation(1, 10) станет десятикратное выполнение инструкций с изменением счетчика от 1 до 10. В данном случае будет напечатано:

Hello N 1
Hello N 2
…
Hello N 10

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

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

Пример 2.

Procedure LoopImitation2(i, n: integer); begin if i

В этом случае, прежде чем начнут выполняться инструкции, произойдет рекурсивный вызов процедуры. Новый экземпляр процедуры также, прежде всего, вызовет еще один экземпляр и так далее, пока не дойдем до максимального значения счетчика. Только после этого последняя из вызванных процедур выполнит свои инструкции, затем выполнит свои инструкции предпоследняя и т.д. Результатом вызова LoopImitation2(1, 10) будет печать приветствий в обратном порядке:

Hello N 10
…
Hello N 1

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

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

Procedure LoopImitation3(i, n: integer); begin writeln("Hello N ", i); {Здесь может располагаться первый блок инструкций} if i

Здесь сначала последовательно выполнятся инструкции из первого блока затем в обратном порядке инструкции второго блока. При вызове LoopImitation3(1, 10) получим:

Hello N 1
…
Hello N 10
Hello N 10
…
Hello N 1

Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.

Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:

Пример 3: Перевод числа в двоичную систему.

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

Взяв же целую часть от деления на 2:

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

While x>0 do begin c:=x mod 2; x:=x div 2; write(c); end;

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

С помощью рекурсии нетрудно добиться вывода в правильном порядке без массива и второго цикла. А именно:

Procedure BinaryRepresentation(x: integer); var c, x: integer; begin {Первый блок. Выполняется в порядке вызова процедур} c:= x mod 2; x:= x div 2; {Рекурсивный вызов} if x>0 then BinaryRepresentation(x); {Второй блок. Выполняется в обратном порядке} write(c); end;

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

4. Рекуррентные соотношения. Рекурсия и итерация

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

Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал

Очередной факториал можно вычислить по предыдущему как:

Введя обозначение , получим соотношение:

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

X:= 1; for i:= 2 to n do x:= x * i; writeln(x);

Каждое такое обновление (x:= x * i) называется итерацией , а процесс повторения итераций – итерированием .

Обратим, однако, внимание, что соотношение (1) является чисто рекурсивным определением последовательности и вычисление n-го элемента есть на самом деле многократное взятие функции f от самой себя:

В частности для факториала можно написать:

Function Factorial(n: integer): integer; begin if n > 1 then Factorial:= n * Factorial(n-1) else Factorial:= 1; end;

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

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

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

При «лобовом» подходе можно написать:

Function Fib(n: integer): integer; begin if n > 1 then Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; end;

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

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

// x1, x2 – начальные условия (1, 1) // n – номер требуемого числа Фибоначчи function Fib(x1, x2, n: integer): integer; var x3: integer; begin if n > 1 then begin x3:= x2 + x1; x1:= x2; x2:= x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; end;

И все же итерационные решения предпочтительны. Спрашивается, когда же в таком случае, следует пользоваться рекурсией?

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

5. Деревья

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

5.1. Основные определения. Способы изображения деревьев

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

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

Рис. 3. Дерево.

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

Графически дерево можно изобразить и некоторыми другими способами. Некоторые из них представлены на рис. 4. Согласно определению дерево представляет собой систему вложенных множеств, где эти множества или не пересекаются или полностью содержатся одно в другом. Такие множества можно изобразить как области на плоскости (рис. 4а). На рис. 4б вложенные множества располагаются не на плоскости, а вытянуты в одну линию. Рис. 4б также можно рассматривать как схему некоторой алгебраической формулы, содержащей вложенные скобки. Рис. 4в дает еще один популярный способ изображения древовидной структуры в виде уступчатого списка.

Рис. 4. Другие способы изображения древовидных структур: (а) вложенные множества; (б) вложенные скобки; (в) уступчатый список.

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

Также можно провести аналогию между уступчатым списком и внешним видом оглавлений в книгах, где разделы содержат подразделы, те в свою очередь поподразделы и т.д. Традиционный способ нумерации таких разделов (раздел 1, подразделы 1.1 и 1.2, подподраздел 1.1.2 и т.п.) называется десятичной системой Дьюи. В применении к дереву на рис. 3 и 4 эта система даст:

1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Прохождение деревьев

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

Алгоритм обхода в прямом порядке:

• Попасть в корень,
• Пройти все поддеревья слева на право в прямом порядке.

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

В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, F, G.

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

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

// Preorder Traversal – английское название для прямого порядка procedure PreorderTraversal({Аргументы}); begin //Прохождение корня DoSomething({Аргументы}); //Прохождение левого поддерева if {Существует левое поддерево} then PreorderTransversal({Аргументы 2}); //Прохождение правого поддерева if {Существует правое поддерево} then PreorderTransversal({Аргументы 3}); end;

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

Алгоритм обхода в обратном порядке:

• Пройти левое поддерево,
• Попасть в корень,
• Пройти следующее за левым поддерево.
• Попасть в корень,
• и т.д пока не будет пройдено крайнее правое поддерево.

То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.

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

// Inorder Traversal – английское название для обратного порядка procedure InorderTraversal({Аргументы}); begin //Прохождение левого поддерева if {Существует левое поддерево} then InorderTraversal({Аргументы 2}); //Прохождение корня DoSomething({Аргументы}); //Прохождение правого поддерева if {Существует правое поддерево} then InorderTraversal({Аргументы 3}); end;

Алгоритм обхода в концевом порядке:

• Пройти все поддеревья слева на право,
• Попасть в корень.

Для дерева на рис. 3 и 4 это даст последовательность узлов: B, D, E, G, F, C, A.

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

// Postorder Traversal – английское название для концевого порядка procedure PostorderTraversal({Аргументы}); begin //Прохождение левого поддерева if {Существует левое поддерево} then PostorderTraversal({Аргументы 2}); //Прохождение правого поддерева if {Существует правое поддерево} then PostorderTraversal({Аргументы 3}); //Прохождение корня DoSomething({Аргументы}); end;

5.3. Представление дерева в памяти компьютера

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

Type PTree = ^TTree; TTree = record Inf: integer; LeftSubTree, RightSubTree: PTree; end;

Каждый узел имеет тип PTree. Это указатель, то есть каждый узел необходимо создавать, вызывая для него процедуру New. Если узел является концевым, то его полям LeftSubTree и RightSubTree присваивается значение nil . В противном случае узлы LeftSubTree и RightSubTree также создаются процедурой New.

Схематично одна такая запись изображена на рис. 5.

Рис. 5. Схематичное изображение записи типа TTree. Запись имеет три поля: Inf – некоторое число, LeftSubTree и RightSubTree – указатели на записи того же типа TTree.

Пример дерева, составленного из таких записей, показан на рисунке 6.

Рис. 6. Дерево, составленное из записей типа TTree. Каждая запись хранит число и два указателя, которые могут содержать либо nil , либо адреса других записей того же типа.

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

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

6.1. Рисование дерева

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

Рис. 6. Деревце.

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

Пример такой процедуры, написанный на Delphi, представлен ниже:

Procedure Tree(Canvas: TCanvas; //Canvas, на котором будет рисоваться дерево x,y: extended; //Координаты корня Angle: extended; //Угол, под которым растет дерево TrunkLength: extended; //Длина ствола n: integer //Количество разветвлений (сколько еще предстоит //рекурсивных вызовов)); var x2, y2: extended; //Конец ствола (точка разветвления) begin x2:= x + TrunkLength * cos(Angle); y2:= y - TrunkLength * sin(Angle); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); if n > 1 then begin Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); Tree(Canvas, x2, y2, Angle-Pi/4, 0.55*TrunkLength, n-1); end; end;

Для получения рис. 6 эта процедура была вызвана со следующими параметрами:

Tree(Image1.Canvas, 175, 325, Pi/2, 120, 15);

Заметим, что рисование осуществляется до рекурсивных вызовов, то есть дерево рисуется в прямом порядке.

6.2. Ханойские башни

Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
В процессе требуется, чтобы больший диск ни разу не оказывался над меньшим. Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности.

Независимо от Брамы данную головоломку в конце 19 века предложил французский математик Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков (рис. 7).

Рис. 7. Головоломка «Ханойские башни».

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

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

Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество дисков.

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

//n – количество дисков //a, b, c – номера штырьков. Перекладывание производится со штырька a, //на штырек b при вспомогательном штырьке c. procedure Hanoi(n, a, b, c: integer); begin if n > 1 then begin Hanoi(n-1, a, c, b); writeln(a, " -> ", b); Hanoi(n-1, c, b, a); end else writeln(a, " -> ", b); end;

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

6.3. Синтаксический анализ арифметических выражений

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

Процесс вычисления арифметических выражений можно представить в виде бинарного дерева. Действительно, каждый из арифметических операторов (+, –, *, /) требует двух операндов, которые также будут являться арифметическими выражениями и, соответственно могут рассматриваться как поддеревья. Рис. 8 показывает пример дерева, соответствующего выражению:

Рис. 8. Синтаксическое дерево, соответствующее арифметическому выражению (6).

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

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

При построении синтаксического дерева следует обратить внимание на следующую особенность. Если есть, например, выражение

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

Аналогично справа налево нужно анализировать выражения, содержащие операторы умножения и деления.

Рис. 9. Синтаксические деревья для выражения a – b + c при чтении слева направо (а) и справа налево (б).

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

7.3. Определение узла дерева по его номеру

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

Например, пусть требуется выполнить k вложенных циклов по n шагов в каждом:

For i1:= 0 to n-1 do for i2:= 0 to n-1 do for i3:= 0 to n-1 do …

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

Procedure NestedCycles(Indexes: array of integer; n, k, depth: integer); var i: integer; begin if depth

Чтобы избавиться от рекурсии и свести все к одному циклу, обратим внимание, что если нумеровать шаги в системе счисления с основанием n , то каждый шаг имеет номер, состоящий из цифр i1, i2, i3, … или соответствующих значений из массива Indexes. То есть цифры соответствуют значениям счетчиков циклов. Номер шага в обычной десятичной системе счисления:

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

M:= round(IntPower(n, k)); for i:= 0 to M-1 do begin Number:= i; for p:= 0 to k-1 do begin Indexes := Number mod n; Number:= Number div n; end; DoSomething(Indexes); end;

Еще раз отметим, что метод не универсален и под каждую задачу придется придумывать что-то свое.

Контрольные вопросы

1. Определите, что сделают приведенные ниже рекурсивные процедуры и функции.

(а) Что напечатает приведенная ниже процедура при вызове Rec(4)?

Procedure Rec(a: integer); begin writeln(a); if a>0 then Rec(a-1); writeln(a); end;

(б) Чему будет равно значение функции Nod(78, 26)?

Function Nod(a, b: integer): integer; begin if a > b then Nod:= Nod(a – b, b) else if b > a then Nod:= Nod(a, b – a) else Nod:= a; end;

(в) Что будет напечатано приведенными ниже процедурами при вызове A(1)?

Procedure A(n: integer); procedure B(n: integer); procedure A(n: integer); begin writeln(n); B(n-1); end; procedure B(n: integer); begin writeln(n); if n

(г) Что напечатает нижеприведенная процедура при вызове BT(0, 1, 3)?

Procedure BT(x: real; D, MaxD: integer); begin if D = MaxD then writeln(x) else begin BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); end; end;

2. Уроборос – змей, пожирающий собственный хвост (рис. 14) в развернутом виде имеет длину L , диаметр около головы D , толщину брюшной стенки d . Определите, сколько хвоста он сможет в себя впихнуть и в сколько слоев после этого будет уложен хвост?

Рис. 14. Развернутый уроборос.

3. Для дерева на рис. 10а укажите последовательности посещения узлов при прямом, обратном и концевом порядке обхода.

4. Изобразите графически дерево, заданное с помощью вложенных скобок: (A(B(C, D), E), F, G).

5. Изобразите графически синтаксическое дерево для следующего арифметического выражения:

Запишите это выражение в обратной польской записи.

6. Для приведенного ниже графа (рис. 15) запишите матрицу смежности и матрицу инцидентности.

Задачи

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

2. Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в строке. При правильной расстановке выполняются условия:

(а) количество открывающих и закрывающих скобок равно.
(б) внутри любой пары открывающая – соответствующая закрывающая скобка, скобки расставлены правильно.

Примеры неправильной расстановки:)(, ())(, ())(() и т.п.

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

Пример неправильной расстановки: ([) ].

4. Число правильных скобочных структур длины 6 равно 5: ()()(), (())(), ()(()), ((())), (()()).
Напишите рекурсивную программу генерации всех правильных скобочных структур длины 2n .

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

(а) если меньшую структуру взять в скобки,
(б) если две меньших структуры записать последовательно.

5. Создайте процедуру, печатающую все возможные перестановки для целых чисел от 1 до N.

6. Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}.

7. Создайте процедуру, печатающую все возможные представления натурального числа N в виде суммы других натуральных чисел.

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

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

10. Создайте процедуру, рисующую кривую Коха (рис. 12).

11. Воспроизведите рис. 16. На рисунке на каждой следующей итерации окружности в 2.5 раза меньше (этот коэффициент можно сделать параметром).

Литература

1. Д. Кнут. Искусство программирования на ЭВМ. т. 1. (раздел 2.3. «Деревья»).
2. Н. Вирт. Алгоритмы и структуры данных.

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

Что такое "рекурсия" вообще?

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

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

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

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

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

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

Деревья рекурсии

Что такое "дерево" в программировании? Это конечное множество, состоящее как минимум из одного узла, который:

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

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

Зачем она применяется в программировании?

Своё применение рекурсия в программировании нашла в решении целого ряда сложных задач. Если необходимо сделать только один вызов, то более легким является применение интеграционного цикла, но при двух и более повторах, чтобы избежать построения цепочки и сделать их выполнение в виде дерева, и применяются рекурсивные ситуации. Для широкого класса задач организация вычислительного процесса таким способом является наиболее оптимальной с точки зрения потребления ресурсов. Так, рекурсия в "Паскале" или другом любом высокоуровневом языке программирования представляет собой вызов функции или процедуры до выполнения условий, независимо от количества внешних вызовов. Другими словами, в программе может быть только одно обращение к подпрограмме, но происходить оно будет до определённого заранее момента. В некотором роде это аналог цикла со своей спецификой использования.

Отличия рекурсии в различных языках программирования

Несмотря на общую схему реализации и конкретное применение в каждом отдельном случае, рекурсия в программировании имеет свои особенности. Это может привести к сложности во время поиска необходимого материала. Но всегда следует помнить: если язык программирования вызывает функции или процедуры, значит, и вызов рекурсии - дело осуществимое. Но наиболее значимые её отличия проявляются при использовании низких и высоких языков программирования. Особенно это касается возможностей программной реализации. Исполнение в конечном итоге зависит от того, какая задача поставлена, в соответствии с ней и пишется рекурсия. Функции и процедуры используются разные, но их цель всегда одна - заставить вызвать самих себя.

Рекурсия - это легко. Как просто запомнить содержание статьи?

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

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

Исходя из технических причин, рекурсия все-таки величина конечная.

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

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

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

Рекурсия в поисковых системах

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

Рекурсивный PageRank oт Google

Такое имя носит алгоритм расчета, созданный и опубликованный Google. Этот алгоритм известен уже давно, но сколько бы раз он не преобразовывался и не дополнялся всевозможными усовершенствованиями, в основе лежит все тот же рекурсивный метод. Суть всегда остается одна и та же: расчеты, перерасчеты и еще раз перерасчеты. В результате получается опять та же функция.

Рекурсивный тИЦ от Яндекса

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

Однако этот показатель на выдачу в Яндексе не влияет. Для этих целей у него есть глубоко спрятанный ВИЦ, который является аналогом PageRank. Так что объем подсчетов у Яндекс также немалый.

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

Представляем функции

• Можно представить функции как чёрные коробки: коробка забирает объект, производит внутри какие-то действия, а потом выплёвывает что-то новое
  • Некоторые функции ничего не забирают (не принимают аргументы), некоторые вообще ничего не делают (они пустые), некоторые не возвращают значения.
  • Наш surfaceAreaCalculator принимает один аргумент (radius), вычисляет площадь поверхности и возвращает результат этого вычисления.
• Функции могут вызывать другие функции
• surfaceAreaCalculator может вызывать функцию square , чтобы получить радиус, возведённый в квадрат, вместо того, чтобы умножать радиус на радиус.
• Мы пишем функции, чтобы облегчить жизнь:
  • такой код легче понимать
  • функции могут переиспользоваться несколько раз

Сравните:

Const surfaceOfMars = surfaceAreaCalculator(3390); // это "ЧТО", в таком виде легче понять суть const surfaceOfMars = 4 * 3.14 * 3390 * 3390; // это "КАК"

Две функции вместе:

const surfaceAreaCalculator = (radius) => { return 4 * 3.14 * square(radius); } const square = (num) => { return num * num; }

Функции, которые вызывают сами себя

• Определение функции - это описание коробки
• Оригинал коробки формируется при вызове функции
• Когда функция вызывает сама себя, создаётся новая идентичная коробка

Перестановки:

• Количество способов перестановки n объектов равно n! (permutations)
• n! определяется таким способом: если n = 1, то n! = 1 ; если n > 0, то n! = n * (n-1)!

Функция, вычисляющая факториал:

Const factorial = (n) =>

Требования рекурсии

1. Простой базовый случай или терминальный сценарий. Простыми словами, когда остановиться. В нашем примере это была 1: мы остановили вычисление факториала, когда достигли 1.
2. Правило двигаться по рекурсии, углубляться. В нашем случае, это было n * factorial(n-1) .

Ожидание умножения

Ничего не умножается, пока мы спускаемся к базовому случаю factorial(1) . Затем мы начинаем подниматься обратно, по одному шагу.

Примечание

Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 - это, в любом случае - 1.

Просто ради забавы

У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска;-)

Опциональные видео

Транскрипт урока

У нас уже есть функция surfaceAreaCalculator , которая принимает один аргумент - радиус - и возвращает площадь поверхности соответствующей сферы, используя формулу 4 * pi * r 2. Помните, мы можем представить функции ящиками: кладём что-то в ящик, она производит какие-то действия и выплёвывает результат.

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

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

Ещё польза в том, что теперь код проще понять. Сравните это:

Const surfaceOfMars = surfaceAreaCalculator(3390);

Const surfaceOfMars = 4 * 3.14 * 3390 * 3390;

Первый вариант намного приятней и проще, особенно для того, кто только что увидел этот код. Первый вариант отвечает на вопрос "что", второй - на вопрос "как".

Const surfaceAreaCalculator = (radius) => { return 4 * 3.14 * square(radius); }

Вместо умножения радиуса на радиус, мы вызовем функцию вычисления квадрата и передадим ей радиус. Очевидно - всё, что делает функция вычисления квадрата, это "принимает число и возвращает его квадрат";

Const square = (num) => { return num * num; }

Давайте отследим шаги и посмотрим, что происходит, когда мы запускаем нашу программу. Мы создаём константу surfaceOfMars и пытаемся сохранить в нее значение, которое возвращает функция surfaceAreaCalculator , когда она вызывается с числом 3390 в качестве аргумента.

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

square хочет умножить n на n и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри surfaceAreaCalculator , который в прямом смысле ждал, пока функция square закончит своё дело. И теперь у нас есть результат вызова square . Он заменяет вызов, поэтому теперь становится возможным завершить умножение и вернуть ответ.

Ответ возвращается и сохраняется в surfaceOfMars .

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

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

Получается шесть уникальных комбинаций из трёх книг. Из четырёх - 24 комбинации. Из 13 - почти столько же сколько людей на планете. 25 книг? Вариантов их перестановки больше, чем атомов во Вселенной.

Вообще, существует n! вариантов перестановки n книг. Факториал означает - умножить все числа от 1 до n. Так что, 3! это 1 * 2 * 3. Давайте напишем функцию факториала.

Const factorial = (n) => { return 1 * 2 * 3 * 4; // oй... }

Ой, подождите. Мы не знаем значение n изначально, в этом вся проблема. Хмм… Как там делается в математике?

А, хорошо, у них там есть два варианта: если n равно 1, тогда факториал - 1, это просто. Но если n не равно 1, тогда факториал - n*(n-1)!

Давайте попробуем вот так:

Const factorial = (n) => { if (n === 1) { return 1; } else { return n * factorial(n-1); } } const answer = factorial(3);

Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

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

Давайте это отследим: мы вызываем factorial(3) . 3 это не 1, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может - ей нужно знать второе число, для чего она вызывает factorial(3-1) или factorial(2) .

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

Формируется новый идентичный ящик factorial , он принимает число 1, и этот ящик уже может мгновенно вернуть ответ - он возвращает 1.

1 возвращается в предыдущий ящик, умножается на 2 и ответ "2" возвращается в предыдущий ящик, умножается на 3 и ответ "6" возвращается во внешний мир и сохраняется в константе answer .

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

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

Давайте проследим шаги ещё раз, но с другой точки зрения, не заглядывая в ящики. Вот как это выглядит пошагово:

Factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;

Умножение не происходит пока мы спускаемся до базового случая функции factorial(1) . А затем мы возвращаемся наверх, производя одно умножение за один шаг.

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

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

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

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

Здравствуй Хабрахабр!

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

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

О рекурсии сказано много. Вот несколько хороших ресурсов:

• Рекурсия и рекурсивные задачи. Области применение рекурсии

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

Задачи

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

Как же решать задачи на рекурсию?

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

из сети

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

Для обоснования можно привести такие доводы.

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

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

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться

Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Итак рекурсивная функция состоит из

• Условие остановки или же Базовый случай
• Условие продолжения или Шаг рекурсии - способ сведения задачи к более простым.

Рассмотрим это на примере нахождения факториала :

Public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться повторять рекурсию? if (n == 1) { return 1; } // Шаг рекурсии / рекурсивное условие return recursion(n - 1) * n; } public static void main(String args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

Теги:

• рекурсия
• задачи
• java

Добавить метки