Рекурсия. Программирование рекурсий на языке Pascal.

Рекурсия

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

Для работы рекурсивной подпрограммы используется стек.
Стек – особая область памяти, в которой хранятся локальные переменные и адреса возврата из подпрограммы. Когда выполняется возврат из рекурсивной подпрограммы, состояние стека изменяется в обратную сторону (“последний вошёл – первым вышел”).

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

Пример:

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

Прямой ход процедуры: 1 2 3 4 5 6 7 8 9 10

Обратный ход процедуры: 10 9 8 7 6 5 4 3 2 1

var n,k:integer;

procedure Print_N(n,k:integer);

begin

write(n,' ');

if n=k then begin writeln;
write('Обратный ход процедуры: ',n,' '); exit;
end;

print_N(n+1,k);

write(n,' ');

end;

begin

write('Прямой ход процедуры: ');

Print_N(1,10);

end.

Пример:
Напечатать последовательность чисел в обратном порядке, используя рекурсивный вызов процедуры. Например: row (5) = 5 4 3 2 1

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

1 procedure row(n:integer);

2 begin

3 if n =1 then begin

4 write (n, ' ');

5 row(n-1)

6 end;

7 end;

8 begin

9 row(5);

10 end.

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

Например:
при переданном функции числе 3078, должно в итоге вернуть 8703.
В процедуре использовать операции div и mod.

1 procedure reverse (n: integer);

2 begin

3 write (n mod 10);

4 if (n div 10) 0 then

5 reverse(n div 10)

6 end;

7 begin

8 writeln;

9 reverse(3078);

10 end.

Пример. Создать рекурсивную функцию для вычисления факториала числа A!

Подсказка:
1!=1

2!=2·1=2

3!=3·2·1=6

...

Выводим рекуррентную формулу a!=a·(a-1)!

var x: integer;

function fact (a: integer): integer;

begin

if (a