Рекурсивные функции
консультация по информатике и икт (11 класс) на тему

Слайд 1

Рекурсивные алгоритмы Задание № 11 Подготовка к ЕГЭ по материалам К.Ю. Полякова

Слайд 2

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

Слайд 3

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

Слайд 4

Задача №1 Алгоритм вычисления значения функции F(x), где n – натуральное число, задан следующими соотношениями: F(1) =1; F(n)=F(n-1)*n, при n>1 Чему равно значение функции F(5)? В ответе записать только натуральное число.

Слайд 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

Слайд 6

Задача №2 Procedure F(n:integer); begin writeln (n); if n<5 then begin F(n+1); F(n+3) end; end. Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1).

Слайд 7

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

Слайд 8

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

Слайд 9

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