2.93M

Category:

programming

Рекурсия. Спиральные рисунки

2.

Напишем процедуру рисования квадрата:
to kv
repeat 4[ fd 150 rt 90 wait 2]
end
Мы добавили в неё команду задержки wait, чтобы
увидеть процесс рисования.

Добавим в процедуру ещё одну команду:
to kv
repeat 4[ fd 150 rt 90 wait 2 ]
kv
End
Назовите словами, что это за команда
это ВЫЗОВ процедуры внутри описания процедуры
Запустим эту процедуру (с вызовом самой себя внутри)
и посмотрим, как она будет исполняться.
Мы увидели бесконечное рисование квадрата!

4.

Немного изменим процедуру:
to kv
repeat 3 [ fd 150 rt 90 wait 2 ]
kv
end
Как она теперь будет работать?
Сделайте и посмотрите!
А что будет, если продолжить изменения и написать
«repeat 2»? а потом «repeat 1»?
Попробуйте сделать!
Вне зависимости от количества шагов цикла процедура
бесконечно рисует квадрат!

5.

«repeat 1» - это отсутствие цикла. Значит, можно
переписать последний вариант записи процедуры:
to kv
repeat 1 [ fd 150 rt 90 wait 2 ]
kv
end
Вот так:
to kv
fd 150 rt 90 wait 2 // здесь нет цикла
kv
end
И процедура опять бесконечно рисует квадрат.

6.

Видим: вызов процедуры внутри самой себя создает
бесконечный цикл.
это
описание
процедуры
(текст)
to kv
fd 150 rt 90 wait
2
kv
end
это вызов
процедуры
на исполнение
(так же мы
вызываем
процедуру в окне
команд)
это рекурсивная процедура
Процедура, внутри описания которой (в качестве одной
из команд) стоит вызов этой же процедуры, называется
рекурсивной,
вызов процедуры из неё же самой называется рекурсия

7.

to kv
Разберемся, как работает
эта рекурсивная процедура и
fd 150 rt 90 wait 2
почему при запуске ее на исполнение
kv
получается бесконечный цикл
end
Блок -схема
Начало
kv
Fd 150
Rt 90
Wait 2
конец
kv
to kv
fd 150 rt 90 wait 2
end
она же, но без рекурсивного вызова
С процедурой без рекурсивного вызова все понятно.
Она выполнилась и остановилась.

8.

to kv
fd 150 rt 90 wait 2
end
Начало
kv
Fd 150
Rt 90
Wait 2
конец
kv
to kv
fd 150 rt 90 wait 2
kv
end
Начало
kv
Fd 150
Rt 90
Wait 2
вызов
kv
конец
kv

9.

to kv
fd 150 rt 90 wait 2
kv
end
Процедура с рекурсивным
вызовом не останавливается.
Квадрат продолжает рисоваться.
Как это происходит?
На следующем слайде
«разрисуем» подробно, как
работает эта блок-схема.
Подумайте:
как исполняется «вызов kv»?
блок-схема
Начало
kv
Fd 150
Rt 90
Wait 2
вызов
kv
конец
kv

10.

Начало
kv
Fd 150
Rt 90
Wait 2
вызов kv = переход в начало kv
Начало
kv
Fd 150
Rt 90
Wait 2
Начало
kv
Fd 150
Rt 90
Wait 2
конец
kv
конец
kv
Работу нижней части блок-схемы
мы пока не увидели
конец
kv

11.

Дальше будет иллюстративное отступление

12.

рекурсивные картинки

13.

14.

15.

16.

17.

Это рекурсивный стих:
…У попа была собака
Он её любил.
Она съела кусок мяса –
Он её убил
И похоронил
И надпись написал,
что
…У попа была собака
Он её любил.
Она съела кусок мяса –
Он её убил
И похоронил
И надпись написал,
что
…У попа была собака
Он её любил.
Она съела кусок мяса –
Он её убил
И похоронил
И надпись написал,
что …

18.

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

19.

20.

21.

22.

23.

Если каждая следующая
ветка спирали
меньше предыдущей
– это скручивающаяся спираль
Если каждая следующая
ветка спирали больше
предыдущей, это
раскручивающаяся
спираль.

24.

Написать процедуру
спирали можно так:
рисования
скручивающейся
TO SPIRAL :A
FD :A RT 90
MAKE “A :A – 5 // изменим значение параметра
SPIRAL :A // потом вызовем процедуру
END
или так:
TO SPIRAL :A
FD :A
RT 90
SPIRAL :A – 5 //меняем значение параметра
// внутри вызова процедуры
END

25.

Это описание процедуры:
SPIRAL :20
FD :20 RT 90
SPIRAL: 15
FD 15 RT 90
SPIRAL: 10
FD 10 RT 90
……..
TO SPIRAL :A
FD :A RT 90
SPIRAL :A – 5
END
Это «каскад»
рекурсивных
вызовов,
который будет
происходить,
когда мы запустим
свою процедуру
со значением
параметра = 20.
Разберемся, что происходит при каждом вызове
рекурсивной процедуры. Пойдем по шагам.

26.

1 шаг: SPIRAL 20
FD :A
RT 90
SPIRAL :A - 5
TO SPIRAL :A
FD :A
RT 90
SPIRAL :A – 5
END
Черепашка продвигается вперед на 20
шагов
поворачивается направо на 90 градусов
Вызывается процедура SPIRAL со
значением параметра = 15
2 шаг: SPIRAL 15
FD :A
продвигается вперед на 15 шагов
RT 90
поворачивается
Вызывается процедура SPIRAL со
значением параметра =10
SPIRAL :A - 5

27.

TO SPIRAL :A
FD :A
RT 90
SPIRAL :A – 5
END
3 шаг: SPIRAL 10
FD :A
RT 90
SPIRAL :A - 5
продвигается вперед на 10 шагов
поворачивается
Вызывается процедура SPIRAL со
значением параметра =5

28.

TO SPIRAL :A
FD :A
RT 90
SPIRAL :A – 5
END
4 шаг: SPIRAL 5
FD :A
RT 90
SPIRAL :A - 5
продвигается вперед на 5 шагов
поворачивается
Вызывается процедура SPIRAL со
значением параметра =0
Что будет происходить дальше? Поэкспериментируйте!
Когда завершится выполнение этой процедуры?
Кажется, что никогда ….
Реально, выполнение завершится при перегрузке памяти
(стека)… с этим мы разберемся в курсе Ардуино

29.

блок-схема
TO SPIRAL :A
FD :A
RT 90
SPIRAL :A – 5
END
Начало
spiral :a
Fd a
Rt 90
вызов
spiral :a - 5
конец
spiral :a

30.

Начало
Spiral 20
Fd 20
Rt 90
вызов spiral :a -5 = переход в начало spiral
Начало
Spiral 15
Fd 15
Rt 90
Начало
Spiral 10
Fd 10
Rt 90
конец
spiral 20
конец
spiral 15
конец
spiral 10

31.

Пока мы видели только то, как работает верхняя
часть блок-схемы, с каскадом вызовов. Она
создает «бесконечное» выполнение программы.
Для остановки выполнения программы с
рекурсией можете использовать
CTRL+BREAK
Задание 1.
Вставьте рекурсию в проект «Секундомер», сделав
движение стрелки бесконечным.

32.

Для остановки процедуры есть команда:
STOP
СТОП
Мы можем ввести условие остановки процедуры,
используя конструкцию:
IF <условие> [STOP]
Структура рекурсивной процедуры с остановкой:
To procedura
команды
if <условие> [stop]
procedura
end

33.

Внесите условие остановки в нашу процедуру:
TO SPIRAL :A
IF :A < 5 [STOP]
FD :A
RT 90
SPIRAL :A - 5
END
Тогда на пятом вызове процедура остановится:
Пятый вызов:
Вторая строка:
SPIRAL 0
IF :A < 5 [STOP]
Процедура
останавливается.

34.

Начало
spiral :a
Начало
spiral :a
Fd a
Rt 90
Fd a
Rt 90
да
вызов
spiral :a - 5
конец
spiral :a
Условие
остановки
истинно?
нет
вызов
spiral :a - 5
конец
Spiral :a

35.

Начало
spiral :a
Fd a
Rt 90
да
Условие
остановки
истинно?
нет
вызов
spiral :a - 5
конец
Spiral :a
На следующем слайде – как это работает, подробно

36.

Красные стрелки - вызовы
Начало
Spiral 20
Fd 20
Rt 90
Условие
остановки
Синие стрелки - возвраты
Начало
Spiral 15
Fd 15
Rt 90
Условие
остановки
Начало
Spiral 10
Fd 10
Rt 90
Условие
остановки
конец
spiral 20
конец
spiral 15
конец
spiral 10

37.

Упражнение: глядя на предыдущий слайд,
нарисуйте в тетради блок схему для вызова вот этой
процедуры spiral с параметром 20
TO SPIRAL :A
IF :A < 15 [STOP]
FD :A
RT 90
SPIRAL :A - 5
END
Проследите, как будет осуществляться возврат из каскада
вызовов. Надо будет проследить «обратный» путь по
синим стрелкам от срабатывания условия останова до
точки «конец spiral 20»

38.

Упражнение: Попробуйте запустить вот такую
процедуру с параметром 10:
TO SPIRAL :A
IF :A > 100 [STOP]
SPIRAL :A + 10
FD :A RT 90
END
Для наглядности можно запустить ее на медленной
скорости или альтернатива - добавить в строку с
рисованием ветки задержку, например wait 10.

39.

А теперь измените ее – поставьте рисование ДО
проверки условия остановки и рекурсивного вызова.
И снова запустите ее на исполнение с параметром 10.
TO SPIRAL1 :A
FD :A RT 90
IF :A > 100 [STOP]
SPIRAL1 :A + 10
END
Что получается?

40.

TO SPIRAL :A
IF :A > 100 [STOP]
SPIRAL :A + 10
после
FD :A RT 90
END
до
см. заметки слайда

41.

Первая процедура нарисует скручивающуюся спираль, а
вторая процедура – раскручивающуюся.
Интересно, как выполняется рекурсия в каждом из случаев?
В первом случае рисование начинается не сразу.
Рисование начнется только после того,
как сработает команда СТОП:
- сначала будет нарисована наибольшая ветка,
которая относится к последнему вызову;
- потом та, которая относится к предпоследнему вызову…
- последней будет нарисована ветка,
относящаяся к первому вызову, с параметром 10
Почему так происходит?

42.

ЭТО ОЧЕНЬ ВАЖНОЕ УПРАЖНЕНИЕ.
К ТОМУ, ЧТО ПРОИСХОДИТ В КАЖДОМ ИЗ СЛУЧАЕВ,
МЫ БУДЕМ ВОЗВРАЩАТЬСЯ В ПРОЦЕССЕ
ДАЛЬНЕЙШЕГО ОБУЧЕНИЯ.
Запоминайте, что вы видите при работе каждой из
процедур на компьютере и что рисуете на листочке

43.

Проследите, как будет выполняться каждая из процедур.
На листочке сделайте 5 шагов
(5 последовательных рекурсивных вызовов):
SPIRAL :10
……
SPIRAL: 20
……
SPIRAL: 30
……
SPIRAL: 40
…..
SPIRAL: 50
…..
TO SPIRAL :A
IF :A > 50 [STOP]
SPIRAL :A + 10
FD :A RT 90
END
TO SPIRAL1 :A
FD :A RT 90
IF :A > 50 [STOP]
SPIRAL1 :A + 10
END

44.

TO SPIRAL :A
IF :A > 30 [STOP]
SPIRAL :A + 10
FD :A RT 90
END
TO SPIRAL1 :A
FD :A RT 90
IF :A > 30 [STOP]
SPIRAL1 :A + 10
END
Изменим условие так, чтобы до останова было всего 3 шага
Упражнение:
1) нарисуйте блок-схему с каскадом вызовов и возвратов для
первой процедуры. Первый вызов с параметром 10, и так далее до
останова, всего 3 шага.
2) с помощью блок-схемы виден ответ на вопрос, почему спираль
получается скручивающейся и почему рисование начинается после
выполнения условия останова.
3) блок-схема для второй процедуры будет аналогична той, что вы
рисовали в предыдущем упражнении, можете воспользоваться ей.
4) сравните на блок-схемах, как работает каждая из процедур.

45.

Задание 2.
1) Написать процедуру рисования квадратной спирали так, чтобы
спираль всегда вписывалась в рабочее поле, была в целом одного
и того же размера, а «плотность» спирали была параметром
процедуры.
2)
Измените
процедуру
так,
чтобы
«раскручивающейся», стала «скручивающейся».
спираль
из

46.

Задание 3.
1) Напишите универсальную рекурсивную процедуру
рисования раскручивающейся N-угольной спирали.
2) Измените ее так, чтобы спираль стала скручивающейся.

47.

Задание 4.
1) Напишите процедуру рисования вот такой кривой.
Процедура должна иметь параметр x
– шаг, который делает черепашка
при рисовании большего полукруга.
На этом рисунке значение параметра
(шага) равно 2. Обратите внимание,
что при завершении рисования
черепашка должна смотреть вниз –
такое
положение
черепашки
потребуется нам для дальнейшего
конструирования сложных фигур из
данной кривой.