1 Программирование на языке Паскаль © К.Ю. Поляков, Введение Введение 2. Ветвления Ветвления 3. Сложные условия Сложные условия 4. Циклы Циклы 5. Циклы с условием Циклы с условием 6. Оператор выбора Оператор выбора 7. Графика Графика 8. Графики функций Графики функций 9. Процедуры Процедуры 10. Рекурсия Рекурсия 11. Анимация Анимация 12. Случайные числа Случайные числа 13.Функции Функции

2 Программирование на языке Паскаль Тема 10. Рекурсия © К.Ю. Поляков,

3 Рекурсивные объекты Рекурсивный объект – это объект, определяемый через один или несколько таких же объектов. У попа была собака, он ее любил. Она съела кусок мяса, он ее убил. В ямку закопал, надпись написал: У попа была собака, он ее любил. Она съела кусок мяса, он ее убил. В ямку закопал, надпись написал: Сказка о попе и собаке Примеры: Сказка о попе и собаке: Факториал: если Рисунок с рекурсией:

4 Дерево Пифагора Дерево Пифагора из N уровней – это ствол и отходящие от него симметрично два дерева Пифагора из N-1 уровней, такие что длина их стволов в 2 раза меньше и угол между ними равен 90 o. 6 уровней: Как доказать, что это рекурсивная фигура? ?

5 Дерево Пифагора Особенности: когда остановиться? деревья имеют различный наклон когда число оставшихся уровней станет равно нулю! (x 1, y 1 ) (x 0, y 0 ) α α+45 o α-45 o L x 1 = x 0 + L · cos(α) y 1 = y 0 – L·sin(α) x 1 = x 0 + L · cos(α) y 1 = y 0 – L·sin(α) наклон "дочерних" деревьев α + π/4 α – π/4 α + π/4 α – π/4

6 Процедура угол α длина ствола procedure Pifagor(x0, y0, a, L: real; N: integer); const k = 0.6; { изменение длины } var x1, y1: real; { локальные переменные } begin if N > 0 then begin x1 := x0 + L*cos(a); y1 := y0 - L*sin(a); Line (round(x0), round(y0), round(x1), round(y1)); Pifagor (x1, y1, a+pi/4, L*k, N-1); Pifagor (x1, y1, a-pi/4, L*k, N-1); end; рекурсивные вызовы закончить, если N=0 Рекурсивной называется процедура, вызывающая сама себя.

7 Программа program qq; procedure Pifagor(x0, y0, a, L: real; N: integer);... end; begin Pifagor (250, 400, pi/2, 150, 8); end; угол α длина ствола число уровней x0x0 x0x0 y0y0 y0y0 Как наклонить дерево вправо на 30 o ? ? Pifagor (250, 400, 2*pi/3, 150, 8);

8 «4»: Используя рекурсивную процедуру, построить фигуру: «5»: Используя рекурсивную процедуру, построить фигуру: Задания