Тема № 5
Рекурсивные вспомогательные алгоритмы 

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

5.1. Рекурсивная процедура

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

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

     Составим головной алгоритм, в котором будет блок обращения к данной процедуре, и проанализируем ее работу. Блок-схема головного алгоритма показана на рис. 2.

Рис. 2. Блок-схема головного алгоритма, содержащего обращение к рекурсивной процедуре

     Итак, в блоке 2 головной алгоритм вызывает процедуру Rec с фактическим параметром 3. Проанализируем работу процедуры. После входа в тело процедуры с параметром a = 3 в блоке 2 процедуры будет проверено условие 3, которое в данном случае имеет вид 3 > 0. Это условие выполняется, следовательно, далее в блоке 3 будет выполнено новое обращение к той же процедуре Rec, но уже со значением a = 2.  Затем аналогично произойдет обращение к Rec(1) и Rec(0). При последнем вызове условие 2 не выполнится и произойдет переход к блоку 4, где будет отпечатано число 0. Теперь произойдет завершение процедуры Rec(1), которая вызывала Rec(0), и будет выполнен блок 4, где будет отпечатано число 1. Аналогично будет завершены вызовы Rec(2) с печатью числа 2 и Rec(3) с печатью числа 3.

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

Рис. 3. Схема последовательности действий при вызове рекурсивной процедуры

     Более наглядное представление о процессе низходящего процедурного углубления и последующего восхождения дает рис. 4.

Рис. 4. Схема последовательности действий процесса рекурсивного спуска и подъема

     Реализуем вспомогательный и головной алгоритмы в среде Delphi.

     Запустим Delphi XE7 и создадим новое приложение. Положите на форму компоненты, как показано на рис. 4. 

Рис. 5. Окно приложения Delphi     

     Код рекурсивной процедуры Rec и обработчика от щелчка на кнопке показан на рис. 6.

Рис. 6. Программный код реализации рекурсивного процесса

     Запустите программу на выполнение и щелкните на кнопке. Получится результат, который показан на рис. 7.

Рис. 7. Окно результатов вызова рекурсивной процедуры

     Дайте объяснение программному коду и получившимся результатам.

5.2. Рекурсивная функция

     Блок-схема алгоритма-функции Fact вычисления факториала числа n показана на рис. 8.

Рис. 8. Алгоритм-функция  вычисления факториала числа

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

5.3. Индивидуальные задания

     Разработайте блок-схемы рекурсивных вспомогательных алгоритмов, головного алгоритма и соответствующую программу на Delphi по своему индивидуальному варианту. Опишите блок-схемы алгоритмов и код программы.      

     Варианты индивидуальных заданий приведены в таблице 1.

Таблица 1