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

Не замечает. Кто ничего Не замечает, Тот ничего Не изучает. Кто ничего Не изучает, Тот вечно хнычет И

скучает.

Автор: Лимаренко Андрей Иванович, учитель информатики гимназии 446,
Санкт-Петербург, Колпино

фрактальной геометрии
построение фрактала с помощью рекурсивного алгоритма.
Повторение графических возможностей

среды быстрой разработки программ Pascal_ABC_Net

Пример самоподобной геометрической фигуры

объект — это объект, … в точности или приближённо совпадающий

с частью себя самого
(то есть целое имеет ту же
форму, что и одна или более
частей).

Шли Из Африки В Саратов Семь
Отчаянных Пиратов Не дошли До Душанбе - Видят надпись на столбе: "Шли Из Африки В Саратов..."
(По Б.Заходеру. Рекурсия.)

ПРИМЕРЫ:

Приведите свои примеры рекурсии:
- из литературы
- из физики
- из химии

нет
Шёл по пустыне караван, Два ишака один баран. Вам эту песню не

понять, И я начну её опять.
Шел по пустыне караван…

неё же самой, непосредственно (простая рекурсия) или через другие функции

(сложная рекурсия).

Например,
функция A вызывает функцию B, а функция B — функцию A.

Количество вложенных вызовов функции называется глубиной рекурсии.

точке (X,Y)
2. Нарисовать окружности радиусом R/2 с новыми координатами:
(X+R;

Y),
(X; Y+R),
(X-R; Y),
(X; Y-R)
3. Для каждой из 4-х окружностей повторить п. 2

Глубина рекурсии алгоритма равна 3

(X,Y)

Y

(Y-R)

(X+R)

(X-R)

X

(Y+R)

факториал определяется так:

n! = 1 · 2 · 3

· … · n

С другой стороны, факториал можно определить следующим образом:

Составьте словесный алгоритм вычисления факториала числа 5

для вычисления факториала числа 5,
необходимо знать значения факториала
числа .

. ., для вычисления факториала числа
. . . необходимо знать значения факториала
числа . . . и т.д.

Вставьте в текст пропущенные слова

f: longint;
n: integer;
function factorial(n:

integer):longint;
begin
if (n=0) or (n=1) then factorial:=1
else factorial:= factorial(n-1)*n;
end;
begin
write(‘n=’); readln(n);
f:=factorial(n);
writeln (n,’! = ‘, f);
readln;
end.

В какой строке программы содержится:
1. Вызов функции? 2. Рекурсия?

процедуры ничем не отличается от . . . другой процедуры.

Что происходит, если одна процедура вызывает другую:
• в памяти размещаются . . ., передаваемые процедуре
• в другом месте памяти сохраняются . . . внутренних переменных вызывающей процедуры;
• запоминается . . . возврата в вызывающую процедуру;
• . . . передается вызванной процедуре.

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

самовызов

вызова

параметры

значения

адрес

управление

состоящий из фрагментов)
— термин, означающий геометрическую фигуру, обладающую свойством

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

Какую связь Вы заметили между фракталом и рекурсией?

знания?
Попробуем применить рекурсивный алгоритм, чтобы из примитивного геометрического объекта получить

объект, похожий на реальный природный.

Эти объекты будут состоять из фрагментов, которые подобны самой фигуре (такие объекты как раз и называют фракталами).

Можно ли применить рекурсивный алгоритм для создания геометрических фракталов?

Программа на PascalABC

а наоборот?
увеличилась (уменьшилась) высота дерева?
увеличить количество веток?
наклонить дерево влево (вправо)?
x,

y - координаты начала линии
alfa - угол наклона линии
m - начальная длина линии
v - количество ветвлений

урока:

как применение рекурсивных алгоритмов обогащает наш инструментарий программиста

как они влияют на компактность, логичность и простоту восприятия алгоритма.

деятельность на уроке.
О каких понятиях вы сегодня впервые услышали ?
Какие

дополнительные знания вы получили об уже знакомых вам понятиях (факториал)?
Какое практическое применение имеют полученные вами знания?
Назовите учебные предметы, где можно использовать знания о рекурсии и рекурсивных алгоритмах?