Рекурсивный алгоритм

ВВЕДЕНИЕ

Тема: Разработка программы с рекурсивным алгоритмом.
Кривая Гильберта

Техническое задание.

Цель: Создать программу, вычерчивающую кривую Гильберта.
Задачи:

1. Изучить необходимую литературу.

2. Изучить фракталы и их составляющие.

3. Разработать программу на СИ+, которая будет вычеркивать кривую.

Рекурсивный алгоритм.

Рекурсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.

Другими словами, рекурсия - способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить само подобие задачи.

Рекурсивный алгоритм (процедура, функция):

Ø алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;

Ø рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.

Адаптивный рекурсивный алгоритм - алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.

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

Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.

Подпрограмма - все, что находится внутри рекурсивной функции.

Дави́д Ги́льберт - немецкий математик-универсал, внёс значительный вклад в развитие многих областей математики. В 1910—1920-е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков. Гильберт разработал широкий спектр фундаментальных идей во многих областях математики, в том числе теорию инвариантов и аксиоматику евклидовой геометрии. Он сформулировал теорию гильбертовых пространств, одной из основ современного функционального анализа.
Давид Гильберт был одним из истинно великих математиков своего времени. Его труды и его вдохновляющая личность ученого оказали глубокое влияние на развитие математических наук вплоть до настоящего времени. Его проникновенная интуиция, его творческая мощь и неповторимая оригинальность математического мышления, широта и разносторонность интересов сделали Гильберта первооткрывателем во многих областях математики. Это была единственная в своем роде личность, глубоко погруженная в свою работу и полностью преданная науке, учитель и руководитель самого высокого класса, вдохновляющий и крайне великодушный, не знающий усталости и настойчивый во всех своих устремлениях.

Кривая Гильберта — это непрерывная кривая, заполняющая пространство. Эти кривые также являются фракталами, они самоподобны; если вы увеличите масштаб и внимательно посмотрите на часть кривой более высокого порядка, то вы увидите, что она выглядит так же, как сама кривая.

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

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

Вот некоторые кривые Гильберта по возрастанию порядка:

Рис.1

От 1D к 2D