Рекурсивные функции

Рекурсивные алгоритмы

Задание №11

Подготовка к ЕГЭ

по материалам К.Ю. Полякова

Рекурсивный алгоритм

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

Что нужно знать:

• Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа.

1 Чему равно значение функции F(5)? В ответе записать только натуральное число. " width="640"

Задача №1

• Алгоритм вычисления значения функции F(x), где n – натуральное число, задан следующими соотношениями:

F(1) =1;

F(n)=F(n-1)*n, при n1

Чему равно значение функции F(5)?

В ответе записать только натуральное число.

Решение:

F(1)=1

F(2)=1*2=2

F(3)=2*3=6

F(4)=6*4=24

F(5)=24*5=120

Нетрудно заметить, что это

F(n)=1*2*3*…*n=n!

Ответ: 120

Задача №2

Procedure F(n:integer);

begin

writeln(n);

if n

begin

F(n+1);

F(n+3)

end;

end.

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1).

5 выполняется два рекурсивных вызова, решать такую задачу удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции): " width="640"

• поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров;
• поскольку при n5 выполняется два рекурсивных вызова, решать такую задачу удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):

Складывая все эти числа, получим ответ - 49

Решение (вариант 2, подстановка):