Readln (kol);

……..

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

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

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

Способ вызова подпрограммы, в котором подпрограмм вызывает сама себя, называют рекурсией.

Подпрограммы, реализующие рекурсию, называются рекурсивными подпрограммами.

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

Пример

Вычисление факториала числа

Обоснование выбора способа реализации.

Обратим внимание на то, что вычислить факториал числа N можно следующим образом:

N! =N*(N-1)!=N*(N-1)*(N-2)! И так далее

То есть для вычисления факториала числа N требуется вычислить факториал числа (N-1), для вычисления факториала (N-1) необходимо вычислить факториал числа (N-2) и так далее. Заметим, что вычисление факториала числа сводится к вычислению факториала числа, на единицу меньше самого числа.

Реализуем такой алгоритм с использованием механизма рекурсии.

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

function Fact (n:byte):integer;

Begin

if n=0 then Fact:=1

else Fact:=n*Fact(n-1);

End;

Здесь имени функции сразу присваивается результат вычисления.

При вызове функции Fact(n-1) согласно оператору Fact:=n*Fact(n-1), где т – параметр функции, вместо n подставляется параметр (n-1) и, следовательно, вычисляется строка n*(n-1)*Fact((n-1)-1) и так далее.

Рекурсивное обращение к функции Fact будет продолжаться до тех пор, пока n не станет равным 0

Домашнее задание

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

Подсказка. Заметим, что Xⁿ = X* X^n-1