Выполнил Багаев Александр Валерьевич, г. Саратов
Рекурсивные Процедуры и Функции
Рекурсия
Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
ИЛИ
Рекурсия – программа или функция является рекурсивной если она вызывает сама себя при условии, что существует какое-то условие, которое останавливает рекурсию. (Иначе это приведет к вечной рекурсии и бесконечному циклу)
Правило создания рекурсии
Пример
def Rec(x):
if x==0:
return 1
else:
Rec(x-1)
print(x)
Rec(3)
Примеры рекурсии
- Круговая
- Звезда Коха
- Дерево
- Фрактал
Фракталы
- Во всех детерминированных фракталах, само-подобие проявляется на всех уровнях. Это значит, что независимо от того насколько вы приближаете фрактал, вы увидите все тот же узор. Для сложных фракталов, которые будут рассмотрены позже, это не так.
ФРАКТАЛ СЕРПИНСКОГО
В этом фрактале, инициатор и генератор одинаковы. При каждой итерации, добавляется уменьшенная копия инициатора к каждому углу генератора и так далее. Если при создании этого фрактала произвести бесконечное число итераций, он бы занял всю плоскость, не оставив ни одной дырочки. Поэтому его фрактальная размерность ln9/ln3 = 2.0
КРИВАЯ КОХА
- Она была изобретена в девятнадцатом веке немецким математиком по имени Хельге фон Кох, который, изучая работы Георга Контора и Карла Вейерштрассе, натолкнулся на описания некоторых странных кривых с необычным поведением. Инициатор — прямая линия. Генератор — равносторонний треугольник, стороны которого равны трети длины большего отрезка. Эти треугольники добавляются к середине каждого сегмента снова и снова.
ФРАКТАЛЫ ЗВЕЗДА И СНЕЖИНКА
- Оба эти объекта не являются классическими фракталами, и они не были изобретены Мандельбротом или кем-либо из известных математиков. Эти фракталы были созданы из интереса, чтобы поэкспериментировать в программировании. И инициатор и генератор здесь фигура, сформированная соединением средних точек сторон со средними точками противолежащих сторон в правильном шестиугольнике.
Задача 1
- Напишите рекурсивную программу для вычисления факториала заданного числа N.
Задача 2
- Напишите программу, которая бы выводила последовательность Фибоначчи до заданного числа.
Замечание:
При работе с рекурсивными функциями можно легко превысить глубину допустимой в Python рекурсии. Для настройки глубины рекурсии следует использовать функцию setrecursionlimit(N)из модуля sys, установив требуемое значение N.
.
Задача 3
- Напишите программу, которая печатает следующий рисунок с помощью рекурсии:
*
* *
* * *
* * * *
* * * * *
* * * * * *
* * * * * * *
* * * * * * * *
Графические библиотеки
- Tkinter
- Pygame
- Pythonwin
- PythonCard
- Turtle
ЧЕРЕПАШКА
Команды рисования: down() #опустить курсор для рисования up() #поднять курсор width(n) #ширина следа курсора в n пикселей сolor(s) #где s #цвет рисования курсора
- Команды для перемещения курсора: forward(n) #вперед на n пикселей backward(n) #назад на n пикселей left(n) #влево на n градусов right(n) #вправо на n градусов
Дополнительно:
Import turtle #подключение библиотеки
reset() #очищается экран, возвращает курсор mainloop() #задержка окна speed(speed) #Установить скорость черепашки. speed должно быть от 1 (медленно) до 10 (быстро), или 0 (мгновенно);
Тренинг
- Потренируйтесь с командами черепашки, разберитесь с ними и попробуйте создать примитивные фигуры
Задача 5
- Попробуйте воссоздать рисунок:
Домашнее задание
- Закрепить материал дома на тему «рекурсия»
- Задача: Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.
