Материал опубликован на образовательном портале Инфо-урок

Планируемые образовательные результаты:

предметные – представления о понятиях «рекурсия»,«глубина рекурсии», «прямой и обратный ход рекурсии»; умение анализировать работу готовых рекурсивных алгоритмов;

метапредметные – умение самостоятельно планировать пути достижения целей; умение соотносить свои действия с планируемыми результатами, осуществлять контроль своей деятельности, определять способы действий в рамках предложенных условий, корректировать свои действия в соответствии с изменяющейся ситуацией; умение оценивать правильность выполнения учебной задачи;

личностные – алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе; представление о программировании как сфере возможной профессиональной деятельности.

1 этап урока: объяснение нового материала:

Слово рекурсия от лат. recursio означает круговорот. Синонимами этого слова являются возвращение, повторение. Классическим примером рекурсивного алгоритма является алгоритм решения задачи "Ханойские башни". Есть три стержня, на одном из которых находятся кольца разного диаметра. Необходимо переложить их с первого стержня на свободный, используя еще один.

Рассмотрим случай с пятью кольцами.

Учащимся предлагается самостоятельно составить алгоритм к этой задаче и устно описать его.

Далее учитель загружает файл Hanoy.exe и демонстрирует учащимся работу алгоритма.

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

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

Рекурсивная (процедура) функция вызывает сама себя напрямую или через другие процедуры и функции. Количество таких вызовов называется глубиной рекурсии.

Классическим примером рекурсивного алгоритма является алгоритм нахождения факториала числа n. Факториал может быть введен с помощью рекуррентной формулы, которая связывает факториал числа с факториалом предыдущего числа.

базовые случаи здесь: 0!=1, 1!=1

рекурентная формула:N!=N*(N-1)! при N>=2

На языке Паскаль функция выглядит следующим образом:

function factorial(N: integer) : longint;

begin

if N = 0 then factorial := 1

else

factorial := factorial(N-1) * N

end;

Что же происходит, если одна функция вызывает другую?

· в памяти размещаются параметры, передаваемые функции

· для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);

· запоминается адрес возврата в вызывающую функцию;

· управление передается вызванной функции.

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

Действия, выполняемые функцией до входа на следующий уровень рекурсии, выполняются на прямом ходу рекурсии, а действия, выполняемые по возврату с более глубокого уровня к текущему, – выполняются на обратном ходу рекурсии.

2 этап: практическая работа за компьютером

Продемонстрируем ход рекурсии. Учащимся предлагается протестировать программу , пошагово проследить, как она работает.

var glubina: integer := 0;

function factorial(N: integer) : longint;

begin

{при входе в функцию увеличиваем переменную, в которой хранится глубина рекурсии}

glubina := glubina + 1;

writeln('Прямой ход рекурсии. Глубина = ', glubina);

result := 1;

if N > 0 then result := factorial(N-1) * N;

Writeln('Обратный ход рекурсии. Глубина = ', glubina);

{при выходе из функции - уменьшаем переменную}

glubina := glubina - 1;

end;

begin

factorial(3);

end.

При запуске этой программы, будет выведено:

Прямой ход рекурсии. Глубина = 1

Прямой ход рекурсии. Глубина = 2

Прямой ход рекурсии. Глубина = 3

Прямой ход рекурсии. Глубина = 4

Обратный ход рекурсии. Глубина = 4

Обратный ход рекурсии. Глубина = 3

Обратный ход рекурсии. Глубина = 2

Обратный ход рекурсии. Глубина = 1

3 этап: закрепление нового материала при решении задач.

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

Writeln(*); в этом случае в задаче возможен вопрос: сколько * выведется на экран после выполнения алгоритма;

Writeln(n); в этом случае может быть задан вопрос :какова сумма всех n, выводимых на экран или потребуется записать последовательность из выводимых n.

Рассмотрим следующую задачу:

procedure F(n: integer);

begin

writeln(n);

if n < 6 then begin

F(n+2);

F(n*3)

end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2). (Автор задачи: Поляков К.Ю.)

Решение:

1) сумму чисел, полученных при вызове F(n) обозначим через S(n).

Согласно алгоритму:

S(n)=n+S(n+2)+S(n*3) при n<6,

S(n)= n,n>=6

2) аккуратно и последовательно выполним вычисления:

s(2)=2+s(4)+S(6), т.е необходимо найти S(4) и s(6).

s(4)=4+s(6)+s(12)

s(6)=6

s(12)=12

s(4)=4+6+12=22

s(2)=2+22+6=30

Ответ 30.

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

procedure F(n: integer);

begin

writeln('*');

if n > 0 then begin

F(n-2);

F(n div 2);

F(n div 2);

end

end;

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?(Автор задачи: Поляков К.Ю.)

1) обозначим через Z(n) количество звездочек, которые выводит программа при вызове F(n)

2) из программы видим, что

Z(n) = 1 при всех n <= 0

Z(n) = 1 +Z(n-2) + Z(n div 2) + Z(n div 2) при n > 0

3) n div 2– это частное от деления n на 2

4) попробуем начать с нуля:

Z(0) = 1

Z(1) = 1 + Z(-1) + Z(0) + Z(0) = 1 + 1 +2* 1 =4

Z(2) = 1 + Z(0) + Z(1) + Z(1) = 1 + 1 + 2*4 = 10

Z(3) = 1 + Z(1) + Z(1)+ Z(1) = 1 +3* 4 = 13

Z(4) = 1 + Z(2) + Z(2) + Z(2) = 1 + 3*10 = 31

Z(5) = 1 + Z(3) + Z(2) + Z(2) = 1 + 13 +2*10 = 34

Можно анализировать с конца, так как мы делали в предыдущей задаче, ответ будет таким же.

Ответ:34

Следующая задача:

Определите, что выведет на экран программа при вызове F(9).

procedure F(n: integer);

begin

if n > 0 then begin

write(n);

F(n - 4);

F(n div 2)

end

end;(Автор задачи: Поляков К.Ю.)

Решение:

1. при вызове F(9) условие n>0 выполняется, распечатывается 9, затем вызывается F(n-4) = F(5), затем вызывается F(n div 2) = F(4); т.е. можно записать, что F(9)= 9 F(5) F(4)

2. аналогично рассматриваем F(5) и F(4)

F(5)= 5 F(1) F(2)

F(4)= 4 F(0) F(2)

теперь неизвестны F(2), F(1)

3. F(2)= 2 F(-2) F(1)

F(1)= 1 F(-3) F(0)=1, т.к при n<=0 ничего не выводится

F(2)= 2 F(-2) F(1) =2 1

F(4)= 4 F(0) F(2) =4 2 1

F(5)= 5 F(1) F(2)=5 1 2 1

F(9)= 9 F(5) F(4)=9 5 1 2 1 4 2 1

Учащиеся могут проверить данную задачу на компьютере, выполнив следующую программу:

program rekyrsia;

procedure F(n: integer);

begin

if n > 0 then begin

write(n);

F(n - 4);

F(n div 2)

end

end;

begin

f(9);

readln;

end.

Последовательность будет аналогичной.

4. Домашнее задание:

выполнить следующие задания из открытого банка заданий ЕГЭ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln('*');

if n > 0 then begin

F(n-3);

F(n-2);

F(n div 2);

end

end;

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? (Автор задачи: Поляков К.Ю.)

5. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln(n);

if n < 5 then begin

F(n+2);

F(n*2)

end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1). (Автор задачи: Поляков К.Ю.)

6. Что выведет программа при вызове F(8)?

procedure F(n: integer);

begin

if n > 3 then begin

write(n);

F(n - 3);

F(n - 2)

end

end; (Автор задачи Е. Филина-Поликарпова)