Лабораторная 1. Рекурсия

  1. Модифицировать программу закраски ограниченной области, преобразовав хвостовую(концевую) рекурсию в цикл (сокращение 1 рекурсивного вызова). Модифицировать полученную программу, заменив рекурсию по горизонтали циклом (сокращение 2 рекурсивных вызовов). Оценить максимальную глубину рекурсии для 3-х версий алгоритма закраски ограниченной области: 1) исходной, 2) с сокращением 1 рекурсивного вызова, 3) с сокращением 2-х рекурсивных вызовов.

  2. Для различных исходных данных научиться предсказывать максимальную глубину рекурсии в алгоритме закраски ограниченной области. Предполагается использование области не более чем из 10 точек, формируемой преподавателем. Проверка производится для трех версий алгоритма на языке, выбранном преподавателем. Каждая версия алгоритма зачитывается после трех верных предсказаний подряд.

  3. Разработать программу построения H-дерева (H-фрактала) (https://en.wikipedia.org/wiki/H_tree). Принцип построения заключается в формировании набора состыкованных центрами, перпендикулярных друг другу отрезков, длина каждого из которых в корень квадратный раз меньше длины предыдущего. Основная функция должна строить набор из трех таких отрезков в виде буквы H и рекурсивно вызывать саму себя для построения следующих троек. Параметры функции: 1) координаты (Y,X) центра буквы H, 2) размер горизонтальной перекладины, 3) текущая клубина рекурсии.

    На вход программа принимает размеры (MaxY,MaxX) прямоугольного поля, первоначальный размер горизонтального отрезка, максимальную глубину рекурсии. Программа выводит набор строк, где знаками "*" отмечен H-фрактал, построение начинается с центра поля.

    Для проверки корректности собственных решений можно использовать программы Hrec и pbm. Hrec строит H-фрактал, а pbm переводит его в графический формат. Программы скомпилированы для платформы Linux x86-64. Пример генерации рисунка фрактала: 

    ./Hrec 800 800 400 7 | ./pbm > result.pbm
    В данном примере в центре поля размером 800 на 800 точек генерируется H-фрактал с размером первоначального горизонтального отрезка в 400 точек. Максимальная глубина рекурсии равна 7. Полученный набор строк конвееризируется на вход программы pbm, которая формирует рисунок и сохраняет его в графическом файле result.pbm (формат PBM, версия P1: https://ru.wikipedia.org/wiki/Portable_anymap)