Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
recurs.doc
Скачиваний:
8
Добавлен:
16.02.2016
Размер:
207.36 Кб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО

УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «информатики и технологии программирования»

Д.Н. Лясин, О.Ф. Абрамова

Использование рекурсивных вызовов в программах на языке Си

Методические указания

Волгоград

2012

УДК 004.056

Рецензент:

Канд. Тех. Наук доцент в. И. Капля

Издается по решению редакционно-издательского совета

Волгоградского государственного технического университета

Лясин, Д.Н. Использование рекурсивных вызовов в программах на языке Си

[Электронный ресурс]: методические указания / Д.Н. Лясин, О.Ф. Абрамова//Сборник «Методические указания» Выпуск 3.-Электрон. текстовые дан.(1файл:207 Kb) – Волжский: ВПИ (филиал) ВолгГТУ,2012.-Систем.требования:Windows 95 и выше; ПК с процессором 486+;CD-ROM.

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

Предназначены для студентов, обучающихся по направлению 230100 "Инфор­матика и вычислительная техника" и направлению 231000 "Программная инженерия" всех форм обучения в рамках курса «Основы программирования».CD-ROM

ÓВолгоградский

государственный технический

университет, 2012 ÓВолжский

политехнический институт, 2012

Лабораторная работа n8. Использование рекурсивных вызовов в программах на языке Си.

Цель работы:

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

Общие сведения:

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

Алгоритм называется рекурсивным, если он прямо или косвенно обращается к самому себе. Часто в основе такого алгоритма лежит рекурсивное определение какого-то понятия. Например, о факториале числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0. Это – рекурсивное определение.

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

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

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

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

Рекурсивные вызовы разделяют на прямые и косвенные. При прямой рекурсии функция вызывает сама себя по следующему шаблону:

void func() { … func(); … }

При использовании косвенной рекурсии вызов осуществляется опосредованно, через вызов другой функции:

void func1() { … func(); //вызываем стороннюю функцию …

} int func() {

… func1(); //рекурсивно вызывается func1

}

В последнем примере, очевидно, косвенно вызываются как функция func(), так и функция func().

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

void func() {

… if (условие_продолжения_рекурсии) func(); … }

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

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

unsigned int fact (unsigned int n)

{ unsigned int f;

f=(n<=1)?1:n*fact(n-1);

return f;

}

Функцию можно вызвать для получения значения факториала целого числа:

int main()

{

cout<<fact(5);

}

Рассмотрим, как рекурсивные будут последовательно возникать рекурсивные вызовы функций для обращения fact(5):

Из рисунка видно, что глубина рекурсии равна 5. Условие окончания рекурсивного вызова сформулировано как n<=1, поскольку вычисление факториала чисел 0 и 1 является тривиальным. В терминах рекурсии вычисление 0! и 1! является базой, относительно которой формулируется и вычисляется факториал любого другого натурального числа. Рекурсивным шагом здесь будет вычисление факториала числа, на 1 меньше аргумента функции.

Рассмотрим примеры рекурсий в различных отраслях знания.

Для математики уже рассмотрено рекурсивное определение факториала. Также рекурсивно определение чисел Фибоначчи:

1, если n=1 или n=2;

fn-1+fn-2, если n>2

Необходимо правда отметить, что при программной реализации алгоритма вычисления i-го числа Фибоначчи использование рекурсии будет неэффективным в связи с избыточными повторными вычислениями для формирования чисел i-1 и i-2. Эффективнее здесь использовать приемы динамического программирования, рассмотрение которых выходит за рамки данных методических указаний.

Замечательным примером рекурсивного (причем бесконечного) построения объекта, являются фракталы. Фрактал  — это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба. На рис. 2 можно увидеть графическое представление множества Мандельброта, определение которого рекурсивно, так как использует для вычисления новых координат точки z на комплексной плоскости их предыдущие значения:

z=z2+c

Рисунок 2. Множество Мандельброта.

Более тривиален принцип построения кривой Коха (рис.3):  берём единичный отрезок, разделяем на три равные части и заменяем средний интервал равносторонним треугольником без этого сегмента. В результате образуется ломаная, состоящая из четырех звеньев длины 1/3 от начального. На следующем шаге повторяем операцию для каждого из четырёх получившихся звеньев и т. д…

Рисунок 3. Этапы построения кривой Коха.

Каждому с детства известен пример рекурсии из лингвистики, которым является замечательное стихотворение Р. Бернса «Дом, который построил Джек» в переводе С. Маршака

Вот дом, Который построил Джек. А это пшеница, Которая в темном чулане хранится В доме,  Который построил Джек А это веселая птица-синица, Которая часто ворует пшеницу,  Которая в темном чулане хранится           …     …

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

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

В классическом определении элемента бинарного дерева можно также заметить элементы рекурсии:

struct node

{

int value; //информационная часть узла дерева

node *left, *right; // адресная часть узла

}

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

void walkTree(node * p)

{

if(p)

{

walkTree(p->left); //обойти левое поддерево

cout << p->value << ' '; //вывод информационной части узла

walkTree(p->right); //обойти правое поддерево

}

}

Рассмотрим алгоритм, реализация которого без использования рекурсии будет неэффективной. Очень популярный алгоритм быстрой обменной сортировки по Хоару, который используется в том числе в стандартной библиотеке языка Си (функция qsort), имеет рекурсивную природу.

Описание работы алгоритма быстрой обменной сортировки:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

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

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

Рассмотрим пример работы алгоритма. Сначала разберемся с алгоритмом разделения массива. Пусть задан массив M:

   40 80 30 50 60 20 10

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