Запълване на Серпински

Досега примерите за рекурсия изискваха едно извикване на рекурсията всеки път. Но понякога се налага да направиш няколко рекурентни извиквания. Ето един добър пример – фрактална математическа конструкция, известна като запълване на Серпински:

Както виждаш, това е колекция от малки квадрати, нарисувани в определен шаблон в квадратна област. Ето как ги рисуваме. Започваме с областта на запълнен квадрат и я разделяме на четири секции:

Взимаме трите квадрата с × през тях – горен ляв, горен десен и долен десен – и ги разделяме на четири части по същия начин:

Продължаваме. Разделяме всеки квадрат с × на четири части и поставяме × в горния ляв, горния десен и долния десен квадрати, но никога в долния ляв.

Когато квадратите са достатъчно малки, спираме да делим. Ако запълним всеки квадрат с × и забравим за всички останали квадрати, получаваме запълване на Серпински. Ето как изглежда:

За да обобщим, ето как рисуваме запълване на Серпински в квадрат:

Забележи, че трябва да извършиш не просто едно, а три рекурентни повиквания. Ето защо избрахме запълването на Серпински, за да онагледим множествената рекурсия.

Можеш да избереш всеки три от четирите квадрата, в които рекурентно чертаеш запълвания на Серпински. Ще получиш като резултат горната рисунка, завъртяна на брой градуси, кратен на 90. (Ако начертаеш рекурентно запълване на Серпински в някакъв друг брой квадрати, няма да получиш интересен резултат.)

Програмата по-долу чертае запълване на Серпински. Опитай да добавиш и махнеш коментарите на някои от рекурентните повиквания, за да получиш ротация:

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.