Рекурсия Pascal-Паскаль

Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.

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

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

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

Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.

Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Рекурсия изнутри

Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:

• в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
• в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
• запоминается адрес возврата в вызывающую процедуру;
• управление передается вызванной процедуре.

Если процедуру вызвать повторно из другой процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.

Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .

Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка «<-» означает выход из нее.

Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Как видно из примера, сначала она растет, а затем сокращается.

Подведем итог.

• рекурсивной называется такая процедура или функция, которая вызывает сама себя;
• для завершения процесса рекурсии в алгоритме рекурсивной функции (процедуры) обязательно должно быть условие, обеспечивающее непосредственное завершение функции (процедуры).

Напишем программу вычисления функции, заданной следующим образом:

Решение: из определения видно, что вычисление функции от аргумента, сводится к вычислению этой же функции от меньшего аргумента, и процесс уменьшения аргумента продолжается до тех пор, пока в качестве аргумента не получится единица. Значение функции от единицы определено.

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

• Определение четности или нечетности аргумента. От этого зависит выбор формулы вычислений;
• Выполнение вычислений. Фактически это будет сводиться к определению нового аргумента функции.

Рекурсивная программа построения снежинки

Написать программу, строящую на экране изображение:

Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.

Как видно из рисунка, здесь опять повторяются одни и те же фрагменты. Построение выполняется так: на окружности заданного радиуса r берется 6 равноотстоящих точек (начиная от угла в 0 0, с шагом ?/3), из каждой точки к центру окружности проводятся радиусы. Затем каждая из этих точек выступает центром новой, меньшей окружности с радиусом r=2 r/5. На каждой меньшей окружности вновь берется 6 равноотстоящих точек, из которых строятся радиусы к центру, и т.д., пока радиус не станет меньше или равен 1.

Пример «Кривой Дракона».

Рассмотрим пример решения еще одной классической задачи: «Кривая Дракона».

Изображение кривой Дракона выглядит так:

Очень красиво, не правда ли. Разберемся, как же эта кривая получается.

Возьмем длинную полоску бумаги и сложим ее пополам, а затем развернем на 90. Если смотреть на полоску сбоку, то получится ломаная линия из двух перпендикулярных участков: см. рис. а. Теперь сложим полоску пополам дважды и также дважды развернем на 90 так, как это показано на рис. б. Получим ломаную линию уже из четырех отрезков, причем угол между смежными отрезками составляет 90. Наконец, если сложение и разворачивание полоски осуществить три раза, то в результате получится фигура, представленная на рис. в. Продолжая этот процесс, можно получить кривую, аналогичную той, которая представлена на рис. 1. Эту причудливую кривую называют кривой дракона. Способ построения подсказывает, что она не имеет самопересечений.

Кривая дракона впервые была описана в популярной литературе в журнале Scientific American в 1967 году. Заметка о ней появилась в колонке “Математические игры”, которую вел Мартин Гарднер. Первоначально использовалось полное название кривой – «дракон Хартера — Хейтуэя», которое ей дал основатель компьютерной фрактальной геометрии Бенуа Мандельброт, именем которого названо знаменитое множество. В дальнейшем стали говорить просто о кривой дракона. Выше мы описали один из алгоритмов построения кривой. На наш взгляд, он несколько запутан (хотя и достаточно прост в реализации). Приведем описание алгоритма построение кривой, близкое к тому, которое использовалось Мартином Гарднером.

Рассмотрим горизонтальный отрезок как кривую дракона нулевого порядка. Разделим отрезок пополам и построим на нем прямой угол, как показано на рис. а).

Получим кривую дракона первого порядка. На сторонах прямого угла снова построим прямые углы (рис. б).

При этом вершина первого угла всегда находится справа, если смотреть из точки A (начала кривой) вдоль первого отрезка кривой, а направления, в которых строятся вершины остальных углов, чередуются. На рис. в) и г) показаны кривые дракона третьего и четвертого порядков соответственно.