Задача №11. Использование рекурсивных алгоритмов.
Автор материалов - Лада Борисовна Есакова.
Рекурсия - это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.
Для того, чтобы задать рекурсию, необходимо описать:
- условие остановки рекурсии (базовый случай);
- рекуррентную формулу.
В программировании если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным.
Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия - основной прием программирования).
Классическим примером рекурсивного алгоритма является описание вычисления факториала:
где F(n-1)=(n-1)!
Рекурсивные алгоритмы вычисления одной функции
Пример 1.
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими рекуррентными соотношениями:
F(n) = 1 при n = 1;
F(n) = F(n − 1) · n при n ≥ 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Решение:
Последовательно найдём значения функции от базового случая F(1) до искомого значения F(6):
F(1) = 1
F(2) = 2
F(3) = 6
F(4) = 24
F(5) = 120
F(6) = 720
Ответ:720
Рекурсивные алгоритмы вычисления нескольких функций
Пример 2.
Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.
Решение:
Последовательно найдём значения функций от базового случая F(1), G(1) до искомых значений F(5), G(5):
F(1) = 1; G(1) = 1;
F(2) = F(1) – G(1) = 1 – 1 = 0;
G(2) = F(1) + 2*G(1) = 1+2 = 3;
F(3) = F(2) – G(2) = 0 – 3 = -3;
G(3) = F(2) + 2*G(2) = 0+6 = 6;
F(4) = F(3) – G(3) = -3 – 6 = -9 ;
G(4) = F(3) + 2*G(3) = -3+12 = 9;
F(5) = F(4) – G(4) = -9 – 9 = -18;
G(5) = F(4) + 2*G(4) = -9+18 = 9.
F(5)/G(5) = -18/9 = -2
Ответ:-2
Рекурсивные алгоритмы выполнения процедур
Пример 3.
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик
|
Python
|
SUB F(n)
PRINT n
IF n < 5 THEN
F(n + 1)
F(n + 3)
END IF
END SUB |
def F(n):
print(n)
if n < 5:
F(n + 1)
F(n + 3) |
Паскаль
|
Алгоритмический язык
|
procedure F(n: integer);
begin
writeln(n);
if n < 5 then
begin
F(n + 1);
F(n + 3)
end
end |
алг F(цел n)
нач
вывод n, нс
если n < 5 то
F(n + 1)
F(n + 3)
все
кон |
Си
|
void F(int n)
{
printf("%d\n", n);
if (n < 5) {
F(n + 1);
F(n + 3);
}
} |
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Решение:
Выпишем последовательно все действия, которые выполнят запускаемые процедуры:
F(1) выполнит следующие действия: Вывод числа 1, F(2), F(4)
F(2) выполнит следующие действия: Вывод числа 2, F(3), F(5)
F(4) выполнит следующие действия: Вывод числа 4, F(5), F(7)
F(3) выполнит следующие действия: Вывод числа 3, F(4), F(6)
F(5) выполнит следующие действия: Вывод числа 5
F(5) выполнит следующие действия: Вывод числа 5
F(7) выполнит следующие действия: Вывод числа 7
F(4) выполнит следующие действия: Вывод числа 4, F(5), F(7)
F(6) выполнит следующие действия: Вывод числа 6
F(5) выполнит следующие действия: Вывод числа 5
F(7) выполнит следующие действия: Вывод числа 7
Просуммируем все числа, выведенные на экран: 1+2+4+3+5+5+7+4+6+5+7 = 49
Ответ: 49
Пример 4.
Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Решение:
Выпишем последовательно все действия, которые выполнят запускаемые процедуры:
F(11) G(10) * F(7) G(6) * F(3) G(2) * F(-1)
Всего на экране будет напечатано 3 «звездочки».
Ответ: 3
Пример 7.36.
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
F(n-3);
F(n-2);
F(n div 2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
Решение:
Для наглядности изобразим схему работы алгоритма в виде дерева:

Причем, распишем до конца каждое значение F(n) только один раз. Например, расписав один раз F(1), мы видим, что она напечатает в результате 5 звездочек. Т.е. F(1) = 5.
Проанализировав дерево, видим, что
F(0) = 1
F(2) = 3 + 2*F(1) = 13
F(3) = 1 + F(0) + 3*F(1) = 1 + 1 + 15 = 17
F(4) = 1 + F(1) + 3*F(2) = 1 + 5 + 3*13 = 45
F(6) = 1 + 3*F(3) + F(4) = 1 + 3*17 + 45 = 46 + 51 = 97
Ответ: 97
Ты нашел то, что искал? Поделись с друзьями!
Благодарим за то, что пользуйтесь нашими публикациями.
Информация на странице «Задача №11. Использование рекурсивных алгоритмов.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.
Публикация обновлена:
08.05.2023