F(n) = 1 при n ≤2; F(n) = F(n -1) + 2 × F(n -2) при n> 2.

Задание 16 часть 1

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

F(n) = n + 1 при n ≤ 2;

F(n) = 2  ·  F(n  − 1) + F(n − 2) при n > 2.

Чему равно значение функции F(4)? В ответе запишите только натуральное число.

Решение

Рекурсия - это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.

Для того, чтобы задать рекурсию, необходимо описать:

- условие остановки рекурсии (базовый случай);

- рекуррентную формулу.

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

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

Классическим примером рекурсивного алгоритма является описание вычисления факториала:

где F(n-1)=(n-1)!

В нашем случае последовательно находим:

F(1) = 2;

F(2) =3;

F(3) = 6 + 2 = 8;

F(4) = 16 + 3 = 19;

Таким образом,

ответ F(4) = 19.

Еще примеры подобных заданий

Пример 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), где n — натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≤ 2; F(n) = F(n -1) + 2 × F(n -2) при n> 2.

12 Следующая ⇒