Рекурсивные объекты. Программирование на алгоритмическом языке

1. Рекурсивные объекты

Программирование на алгоритмическом языке
1
Рекурсивные объекты
Сказка о попé и собаке:
Примеры:
У попа была собака, он ее любил.
Она съела кусок мяса, он ее убил.
В ямку закопал, надпись написал:
Сказка о попé и собаке
Рисунок с рекурсией:
Факториал:
1,
если N 1,
N !
если N 1.
N ( N 1)!,
1! 1, 2! 2 1! 2 1, 3! 3 2! 3 2 1
4! 4 3! 4 3 2 1
N ! N ( N 1) 2 1
Рекурсивный объект – это объект, определяемый через
один или несколько таких же объектов.
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

2. Рекурсивная фигура

Программирование на алгоритмическом языке
2
Рекурсивная фигура
3 уровня:
? Где рекурсия?
Фигура из N уровней – это
• окружность и
• 4 фигуры из N-1 уровней
N-1
N-1
N-1
N-1
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

3. Рекурсивная фигура: алгоритм

Программирование на алгоритмическом языке
3
Рекурсивная фигура: алгоритм
(x,y-R)
центр
радиус
уровней
алг РекОк(цел x, y, R, N)
(x,y) (x+R,y)
нач
окончание рекурсии
если N <= 0 то выход все
(x-R,y)
окружность(x, y, R)
(x,y+R)
РекОк(x, y-R, div(R,2), N-1)
РекОк(x+R, y, div(R,2), N-1)
рекурсивные
РекОк(x, y+R, div(R,2), N-1)
вызовы
РекОк(x-R, y, div(R,2), N-1)
кон
Рекурсивный алгоритм – это алгоритм, который
вызывает сам себя (с другими параметрами!).
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

4. Рекурсивная фигура: программа

Программирование на алгоритмическом языке
4
Рекурсивная фигура: программа
использовать Рисователь
алг Рекурсия
нач
РекОк(200, 200, 100, 3)
кон
алг РекОк(цел x, y, R, N)
нач
...
кон
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

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

Программирование на алгоритмическом языке
5
Рекурсивные алгоритмы
• вызывают сами себя прямо
A
прямая рекурсия
• … или через другой алгоритм:
A
B
косвенная рекурсия
• должно быть условие окончания рекурсии (иначе?)
• рекурсия может стать бесконечной
• все задачи могут быть решены без рекурсии, но…
• часто рекурсивные алгоритмы проще и понятнее
• как правило, алгоритмы без рекурсии работают
быстрее и требуют меньше памяти
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

6. Задания

Программирование на алгоритмическом языке
6
Задания
«3»: Нарисовать рекурсивную
фигуру, число уровней вводить с
клавиатуры:
«4»: Нарисовать рекурсивную фигуру,
число уровней вводить с
клавиатуры:
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

7. Задания

Программирование на алгоритмическом языке
7
Задания
«5»: Нарисовать рекурсивную фигуру,
число уровней вводить с
клавиатуры:
К. Поляков, 2010-2011
http://kpolyakov.narod.ru