- Определение рекурсии, рекурсивного алгоритма
- Решение задач
- знать, что такое рекурсия
- уметь разрабатывать программы с использованием рекурсий на языке программирования Паскаль
- Почему подпрограммы на языке программирования Паскаль принято делить на процедуры и функции?
- Что значит «вызвать» подпрограмму?
- В чём состоит парадигма структурного программирования?
Определение рекурсии, рекурсивного алгоритма
Из курса математики вы знаете о методе индукции, когда элемент какого-либо множества определяется на основании уже определённых базовых элементов по некоторому правилу. Например, числа Фибоначчи. Каждое последующее число ряда является суммой двух предыдущих. При этом первые два элемента ряда заранее известны — это 1 и 1:
1, 1, 2, 3, 5, 8, 13 и т. д.
В информатике задачи, в которых известен некоторый базовый набор элементов и правило получения следующего элемента могут решаться с помощью рекурсии.
Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.
Функция (процедура) является рекурсивной, если она вызывает сама себя.
Пример 1
Рассмотрим, как построить рекурсивный алгоритм для нахождения n-го числа Фибоначчи.
Решение
Можно заметить, что n-е число Фибоначчи является суммой двух предыдущих чисел, т. е. Fn = Fn-1 + Fn-2. Соответственно, каждое стоящее перед ним число получается аналогичным способом до тех пор, пока мы не дойдём до двух самых первых чисел. Они нам даны: F1 = 1; F2 = 1.
Иначе описанные соотношения можно записать так:
F(n) = 1 при n <= 2;
F(n) = F(n − 1) + F(n − 2), при n > 2.
Т. е. при n <= 2 вызов рекурсии прекращается (это условие выхода).
function fib(n: integer ): integer ;
begin
if n<=2 then fib:=1
else fib:=fib(n-1)+fib(n-2)
end;
var n: integer ;
begin
readln(n);
writeln(fib(n));
end.
Необходимо отметить, что применение рекурсии не всегда является оптимальным способом решения задачи. В некоторых случаях рекурсия очень замедляет работу программы: для каждого вызова необходимо использовать стековую память. При этом если стековая память закончится, то программа завершится аварийно. Любой рекурсивный алгоритм можно написать с использованием циклов и массивов не рекурсивным способом.
Упражнение 1
Найдите сумму цифр числа с помощью рекурсивного алгоритма.
Пример 2
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1 при n = 1,
F(n) = n + F(n − 1), если n чётно,
F(n) = 2· F(n − 2), если n > 1 и n нечётно.
Чему равно значение функции F(20)?
Решение
Обратим внимание, что в задаче речь идёт о рекурсивной функции.
Для решения данной задачи мы можем написать следующую программу:
function f(n: integer ): integer ;
begin
if n=1 then f:=1;
if (n mod 2 = 0) and (n>1) then f:=n+f(n−1);
if (n mod 2 <> 0) and (n>1) then f:=2*f(n−2);
end;
var n: integer ;
begin
writeln(f(20));
end.
Ответ: 532.
Упражнение 2
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 2 * n при n <= 5,
F(n) = F(n − 2) + 3*F(n/2) , если n — чётно и n > 5,
F(n) = F(n − 1) + F(n − 2) + F(n − 3), если n > 5 и n — нечётно.
Чему равно значение функции F(10)+F(20)?
Пример 3
У исполнителя Сумматор есть 2 команды:
- Прибавь 1,
- Умножь на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом будет число 20?
Решение
Обозначим количество программ, с помощью которых можно получить некоторое число n как f(n). Число меньше 5 (при заданных условиях) получить нельзя. Поэтому при n < 5 количество программ f(n) = 0. Для начального числа 5 существует только одна пустая программа, которая не содержит ни одной команды. Т. е. при n = 5 f(n) = 1. Любое число от 5 до 20 может быть получено из чисел n − 1 и n div 2.
Соответственно f(n) = f(n−1) + f(n div 2).
Запишем полученные соотношения:
f(n) = 0 при n < 5;
f(n) = 1 при n = 5;
f(n) = f(n−1) + f(n div 2) при n > 5.
Далее эту задачу можно написать на языке программирования Паскаль (в виде рекурсивной функции), а можно составить следующую таблицу.
Таблица 1. Пример 3 (решение в виде таблицы)
Ответ: 8.
Упражнение 3
У исполнителя Сумматор есть 3 команды:
- Прибавь 1,
- Прибавь 2,
- Умножь на 2.
Первая команда увеличивает число на экране на 1, вторая прибавляет к нему 2, а третья умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 8 результатом будет число 18?
Итоги
- Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
- Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.
- Функция является рекурсивной, если она вызывает сама себя.
- Примером рекурсии (самоподобной структуры) являются матрёшки или геометрические фракталы.
Контрольные вопросы
- Что такое рекурсия? Рекурсивный алгоритм? Рекурсивная функция?
- Как предотвратить бесконечное выполнение рекурсии?
- В каких случаях удобно использовать рекурсию?
- Приведите примеры рекурсии, которые можно встретить в живой природе.
Упражнение 1
function sum(n: integer ): integer ;
var d,s: integer;
begin
if n=0 then sum:=0
else
begin
d:=n mod 10;
s:=sum(n div 10);
sum:=s+d
end;
end;
var n,i: integer ;
begin
readln(n);
writeln(sum(n));
end.
Упражнение 2
function f(n: integer ): integer ;
begin
if n<=5 then f:=2*n;
if (n mod 2 = 0) and (n>5) then f:=f(n-2)+ 3*f(n div 2);
if (n mod 2 <> 0) and (n>5) then f:=f(n-1)+f(n-2)+f(n-3);
end;
var n,i: integer ;
begin
writeln(f(10)+f(20));
end.
Ответ: 1 120.
Упражнение 3
92
