Рекурсивные функции

Лабораторная работа № 9

Рекурсивные функции

1. Понятие рекурсии.

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

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

В реальном мире рекурсия может проявляться в виде всевозможных форм, связей, определений, структур, способов рассуждений, методов познания и иных действиях. Каждому приходилось видеть изображение, повторяющееся в двух зеркалах, установленных друг против друга или рекламную картинку, на которой изображена та же самая картинка и т. д. Деревья, растения, реки, облака, повторяя себя в своих частях, имеют рекурсивное строение. Размножение вирусов и молекул ДНК связано с рекурсивными процессами. Музыкальные формы и действия также могут быть рекурсивными. Например, в каноне основная мелодия сопровождается той же мелодией, но с задержкой по времени. Наиболее ярко рекурсивность проявляется в процессе развития природы, человека и общества. В клетке заложена информация обо всем организме, дети “повторяют” своих родителей, а общество и материя развиваются по сложной рекурсивной спирали. В некоторых восточных религиях рекурсивность Вселенной подчеркнута её изображением в виде змея, пытающегося проглотить самого себя, начиная с хвоста. Эволюция Вселенной также в какой-то степени подчинена законам рекурсивного развития.

Нетрудно увидеть наличие рекурсивности в структуре или содержании следующих текстов:

· Я знаю, что я ничего не знаю (Сократ);

· Всё трудно до тех пор, пока не станет легким (Т. Фуллер);

· Замени x этим предложением;

· В этой фразе двадцать восемь букв;

· Девять слов назад это предложение ещё не началось (C. Л. Табачников);

2. Рекурсия в информатике.

Информатика и математика в соответствии со своими внутренними содержательными задачами трактуют понятие “рекурсия”, не противореча друг другу, но не совсем одинаково. В информатике рекурсия используется как практически ориентированное знание - инструмент для реальных вычислений.

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

Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. Вычисления, проводимые с помощью рекурсивных алгоритмов (процедур, функций), носят название рекурсивных вычислений.

Различают прямую и косвенную рекурсию. Под прямой рекурсией подразумевают непосредственный вызов алгоритма (функции) F из текста самого алгоритма F. Косвенная (взаимная) рекурсия порождает циклическую последовательность вызовов нескольких алгоритмов F₁, F₂, …, F_k друг друга: F₁ вызывает F₂, F₂ вызывает F₃, …, F_k вызывает F₁ (k>1).

3. Решение задач рекурсивным способом.

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

1. Под параметризацией задачи понимают выявление совокупности исходных величин, определяющих постановку и решение задачи. Значения этих параметров или некоторых из них влияют на трудоемкость решения задачи. Иногда на этапе параметризации необходимо бывает ввести дополнительные параметры, помогающие организовать рекурсию.

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

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

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

Вначале происходит запоминание текущего состояния программы, необходимого для продолжения вычислений, когда управление снова вернется к ней. Затем F с новыми значениями аргументов начинает выполняться заново как бы с новым экземпляром программы. При следующем рекурсивном вызове F все повторяется, и так до тех пор, пока очередной вызов F не приведет к какому-либо элементарному случаю, разрешаемому без рекурсивных вызовов. Далее в порядке, обратном тому, в котором запоминались вызовы, организуются возвраты управления, при этом каждый раз производится чистка памяти, т.е. очередная группа «отработавших» значений локальных переменных уничтожается. Вычисления по рекурсивным функциям носят название отложенных вычислений.

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

4. Примеры решения задач рекурсивным способом.

4.1. Алгоритм Евклида.

Великому древнегреческому математику Евклиду, жившему в Александрии в III веке до нашей эры, автору трактата по геометрии “Начала”, принадлежит способ (метод, алгоритм) нахождения наибольшего общего делителя двух целых чисел, двух многочленов, общей меры двух отрезков. Этот способ, описанный Евклидом в геометрической форме, порождает явно рекурсивный вычислительный процесс. Суть его в следующем.

Даны два целых числа x и y. Последний отличный от нуля остаток при последовательных делениях большего из x, y на меньшее и заменах большего остатком равен nod(x, y).

Доказательство этого утверждения базируется на следующих двух фактах:

· если x делится на у, то nod(x, y)=y;

· если x=y×q+r (0<r<y), где x, y отличны от нуля, то nod(x, y)=nod(y, r).

Из алгоритма Евклида вытекает существование наибольшего общего делителя для любых двух целых x и y, одновременно не равных нулю.

При любых целых неотрицательных числах x и y (x³y или x<y) имеет место соотношение

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

функция nod(целое a, целое b)

{

если b=0 то f= a

иначе f= nod(b, a % b);

nod=f;

}

Параметры: функция nod(целое a, целое b)

База: если b=0 то nod = a

Декомпозиция: nod= nod(b, a % b);

Рассмотренная задача имеет следующее естественное обобщение: составить рекурсивную функцию, возвращающую НОД нескольких целых чисел x₁, x₂, …, x_n (n>2). Замечание: в задаче следует использовать тот факт, что

12 3 Следующая ⇒