Понятие рекурсии

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

С помощью рекурсии удобно представлять те задачи, которые сводятся к подзадачам того же типа, но меньшей размерности. Например: n! = n×(n-1)!. Здесь задача о вычислении n! может быть решена, если решена задача о вычислении (n-1)! и так далее.

Задача 20. Рассмотрим использование рекурсии при написании программы по вычислению n! Значение n (n £ 20) возьмём из текстового файла, туда же запишем результат вычисления.

function fact(k : integer): int64;

begin

if k=1 then fact:=1

else fact:= k * fact(k-1)

end;

procedure TForm1.Button1Click(Sender: TObject);

var n : integer; f:textfile;

begin

assignfile(f, ' n.txt'); reset(f);

readln(f, n);

append(f);

writeln(f, ' n! = ' , fact(n));

closefile(f);

memo1.Lines.LoadFromFile(' n.txt ');

end;

Проследим выполнение этой программы в пошаговом режиме. Предположим, n равно 4. После вызова функции fact формальный параметр k получает значение 4. При выполнении функции сначала проверяется условие k=1. Так как оно не выполнено, то управление передаётся оператору присваивания fact:=k * fact(k–1), при выполнении которого происходит вызов функции fact, но уже для значения k на единицу меньше. Снова происходит проверка условия k=1 и, так как оно опять не выполнено, то снова вызывается fact для значения k на единицу меньше. При достижения условия завершения входа в рекурсию (k=1) получим fact:=1, после чего происходит выход из рекурсии:

k=2 fact:= k * fact(k–1) = 2*1 = 2

k=3 fact:= k * fact(k–1)= 3*2 = 6

k=4 fact:= k * fact(k–1)= 4*6 = 24

Задача 21. Описать рекурсивную функцию для подсчёта количества запятых в данном текстовом файле.

Файловая переменная f должна быть описана в интерфейсной части модуля.

function kol:integer;

var d:char;

begin

read(f, d);

if d=#26 then kol:=0

else if d=' , ' then kol:=kol + 1 else kol:=kol

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

memo1.Lines.LoadFromFile(' w.txt ');

assignfile(f,' w.txt '); reset(f);

label1.Caption:=' Ответ ' + inttostr(kol);

closefile(f)

end;

Задачи

Задача 22. Описать рекурсивную функцию

function step(z : real; m:byte):real;

для вычисления z^m (z – вещественное, m – натуральное) и с её помощью подсчитать значение выражения a⁷ + b⁸ .

Задача 23. Описать рекурсивную функцию

function fib(n : integer) : integer;

для вычисления n-ого (n £ 40) числа Фибоначчи.

Указание. Последовательность чисел Фибоначчи f_k образуется так:

f₀=1, f₁=1, f_k = f_k-2 + f_k-1.

Задача 24. Описать рекурсивную функцию

function arifm(a, d, k : integer) : integer;

для вычисления k-ого элемента арифметической прогрессии (a – первый элемент прогрессии, d – разность прогрессии).