Рекурсивные функции
Классификация и стек рекурсивных функций. Методика распознавания формулы, записанной в строке. Реализация салфетки Серпинского и задачи о Ханойских башнях. Алгоритм быстрой сортировки. Создание функции, сортирующей массив с использованием рекурсии.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 06.07.2009 |
| Размер файла | 160,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Кафедра: Автоматика и Информационные Технологии
Рекурсивные функции
1. Основные понятия рекурсии
1.1 Классификация рекурсивных функций
Определение. Рекурсивной называют функцию, которая прямо или косвенно сама вызывает себя.
Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна.
Если в теле функции явно используется вызов этой же функции, то имеет место прямая рекурсия.
Рекурсия называется однократной, если функция вызывает саму себя один раз. Если функция вызывает саму себя два раза, то рекурсия называется двукратной и т.д.
1.2 Стек рекурсивных функций
При каждом обращении к рекурсивной функции в стеке выделяется место для:
- адреса возврата в вызывающую функцию и вершины стека вызывающей функции (4 байта),
- списка фактических параметров (может быть пустым),
- локальных переменных рекурсивной функции (могут отсутствовать).
Определение. Схемой стека вызовов функций называется последовательность экземпляров функций, вызывающих друг друга.
Для просмотра стека вызовов Borland C++ существует команда отладчика Debug - Call Stack… (Ctrl + F3). В служебном окне выводится список функций, начинающийся с main, которые вызывают друг друга на каждом шаге отладки.
Мы будем использовать другое графическое представление схемы стека вызовов.
1.3 Примеры стека функций
Пример 1.
main ()
{f();}
f()
{}
Схема стека представлена на рис. 1.
Рис. 1. Схема стека вызовов
Здесь символ O означает вызов функции, горизонтальные линии символизируют фрагмент ОЗУ с областью кода соответствующей функции или экземпляра функции. Стрелки указывают ход выполнения программы.
Глубина стека - 2, ширина - 1.
Пример 2.
main()
{f(); g();}
f()
{}
g()
{}
Схема стека представлена на рис. 2.
Рис. 2. Схема стека вызовов
Глубина стека - 2, ширина - 2.
Пример 3.
main()
{f();}
f() 0
{g();}
g()
{}
Схема стека представлена на рис. 3.
Рис. 3. Схема стека вызовов
Глубина схемы - 3, ширина - 1.
Пример 4. (Бесконечная явная рекурсия)
main()
{f();}
f()
{f();}
Схема стека представлена на рис. 4.
Рис. 4. Схема стека вызовов
Ширина схемы - 1, глубина - ?.
Возврата из рекурсии нет. В результате произойдет переполнение стека программы. Посмотрим, что произойдет в случае компиляции программы в модели large (рис. 5).
Рис. 5. Схема ОЗУ
При каждом рекурсивном вызове f() в стек помещаются 4 байта и значение беззнакового двухбайтового регистра SP уменьшается на 4. При переходе через ноль регистр примет значение равное 64К_1. Дальнейшие вызовы приведут к повреждению кучи и к порче занятой части стека. Адрес возврата из программы в оболочку Borland C++ будет изменен и приложение «повиснет».
Отсюда вытекает
Основное правило рекурсии: До рекурсивного вызова должна стоять проверка на возврат из рекурсии.
Будем обозначать эту проверку символом X.
2. Примеры рекурсивных функций
2.1 Пример. (Однократная явная рекурсия)
Вычислить n!=1·2·…·n.
float fact (int n);
void main()
{
float res=fact(3);
printf («%f», res);
}
float fact (int n)
{
if (n==1) return 1;
else return n·fact (n_1);
}
Глубина - n+1, ширина - 1. Схема стека вызовов представлена на рис. 6.
Рис. 6. Схема стека вызовов
2.2 Пример. (Двукратная явная рекурсия)
Вычислить функцию Фибоначчи.
F0 = F1 = 1,
Fn = Fn-1 + Fn-2, n=2,3,…
Легко подсчитать первые члены этой последовательности.
{1, 1, 2, 3, 5, 8, 13, 21, 34…}
float Fib (int n);
main()
{
printf («%f», Fib(4)); // F4=5
}
float Fib (int n)
{
if (n==0 || n==1)
return 1;
else
return Fib (n_1)+Fib (n_2);
}
Очевидно, максимальная глубина стека вызовов (рис. 7) равна n+1, ширину стека вычислить непросто - нижний край неровный. Оценим ширину стека сверху на уровне максимальной глубины числом 2n-1. Тогда количество вызванных экземпляров функции Fib может достигнуть величины 1+21+22+ … +2n-1=2n-1.
Рис. 7. Схема стека
Рекурсивные функции по-разному используют основные вычислительные ресурсы компьютера: память (стек программы) и время работы программы.
Однократная рекурсия образует глубокий стек вызовов единичной ширины и быстро заполняет стек. Время работы программы до переполнения стека ничтожно мало.
Двукратная рекурсия наоборот образует широкий стек вызовов, ширина которого растет экспоненциально. Количество экземпляров рекурсивной функции растет лавинообразно. Это приводит к резкому замедлению работы программы. При этом размер стека программы растет линейно с ростом глубины стека.
Так вызов функции Fib (50) повлечет вызов 250 = 1 Пентабайт экземпляров Fib, в то время как стек программы будет максимально содержать 50·(2+4)=300 байт.
2.3 Пример. (Распознавание формулы, записанной в строке)
Формула содержит: вещественные константы, переменную x и операции «+», «-», «*», «/».
#define NO_OPERATION -1
#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
#include … // подключение заголовочных файлов
float parsing (char *str, float x);
void main()
{
char *str=» 2+2_x-x»;
printf («%f», parsing (str, 3)); // -2
}
float parsing (char * str, float x)
// функция разделения строки на две части
{
char * substr1 = NULL, * substr2 = NULL;
// substr1 - левая часть строки перед знаком
// substr2 - правая часть после знака
char * ptr = NULL;
float y, z;
// y - промежуточная переменная для хранения левого операнда,
// z - для правого, x и y рекурсивно вызывают parsing
char op = NO_OPERATION;
// op - операция (+, -, *, /)
// поиск первого появления знака `+' и перевод указателя на этот знак
if ((ptr = strchr (str, '+'))!= NULL)
op = ADD; // 0
// аналогичный поиск знака `-', `*', `/' но с конца строки
else if ((ptr = strrchr (str, '-'))!= NULL)
op = SUB; // 1
else if ((ptr = strchr (str, '*'))!= NULL)
op = MUL; // 2
else if ((ptr = strchr (str, '/'))!= NULL)
op = DIV; // 3
if (op!= NO_OPERATION)
{
substr1 = (char *) malloc ((int) (ptr - str) + 1);
// память под левую подстроку плюс один знак для конца строки
if (substr1 == NULL)
{
printf («\nERROR: No memory.\n»);
exit (1);
}
substr2 = (char *) malloc (strlen(str) - (int) (ptr-str));
// память под правую подстроку
if (substr2 == NULL)
{
free (substr1);
printf («ERROR: No memory.\n»);
exit (1);
}
// запись в substr1 первых ptr-str символов…
// …строки str и конца строки
strncpy (substr1, str, (int) (ptr-str));
substr1 [(int) (ptr-str)] = '\0';
// запись в substr2, начиная с ptr+1 до конца строки str
strcpy (substr2, ptr+1);
y = parsing (substr1, x);
// вычисляем формулу левой подстроки
z = parsing (substr2, x);
// вычисляем формулу правой подстроки
switch (op)
{
case ADD: y += z;
break;
case SUB: y -= z;
break;
case MUL: y *= z;
break;
case DIV: if (z == 0)
{
printf («\nДеление на ноль»);
exit(1);
}
y /= z;
break;
}
free (substr1);
free (substr2);
return y;
} // if op
else if (! strcmp (str, «x»))
// str совпадает с «x», возвращаем x
return x;
else
// str содержит только вещественную константу
return atof (str);
}
Схема стека вызовов представлена на рис. 8. Первые четыре креста - условия на выход из parsing, пятый крест - совпадение строки с «x» и return x, третий крест - совпадение строки с вещественной константой и return atof(str). Первый круг - y, второй - z. Между ними операция. Глубина стека равна n, где n+1 - количество операций.
Рис. 8. Схема стека
Таким образом, имеем явную двукратную рекурсию.
Недостатки рассмотренной функции parsing.
- Для некоторых строк двукратная рекурсия вырождается в однократную. Например, для строки «x+x+x+x+x+x+x+x» схема стека вызовов будет иметь глубину 7, а ширину всегда 2. В результате будет забиваться стек. Лучше искать среднюю операцию. Тогда бинарное дерево стека вызовов будет сбалансированным.
- Функция parsing для каждого х будет создавать бинарное дерево стека вызовов. Это может привести к замедлению счета, например при построении графиков. Лучше один раз рекурсивным способом построить промежуточную строку, содержащую польскую запись формулы. Затем формула будет вычисляться по промежуточной строке для каждого х не рекурсивно.
2.4 Пример. (Салфетка Серпинского)
Реализовать «салфетку Серпинского» (геометрический фрактал). Как она образуется? Рисуется треугольник и в нем средние линии. В образованных при углах исходного треугольника новых треугольниках опять рисуются средние линии и так далее до заданного порядка вложенности рекурсии.
Рис. 9. Салфетка Серпинского
2.5 Пример. (Задача о Ханойских башнях)
Имеются три стержня с номерами 1, 2, 3. На стержень 1 надето n дисков различного диаметра так, что они образуют пирамиду (рис. 9). Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра. Доказано, что для n дисков минимальное число необходимых перемещений равно 2n-1.
Рис. 10. Ханойские башни
Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие - перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n_1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n_1 диск из w на стержень j, используя, вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n_1 диска и одной простейшей задаче. Схематически это можно записать так: T (n, i, j, w) = T (n_1, i, w, j), T (1, i, j, w), T (n_1, w, j, i).
Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn (n, i, j, w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i, j, w} = {1,3,2}.
#include <stdio.h>
void tn (int, int, int, int); /* функция */
main() /* вызывающая */
{
int n;
scanf («%d»,&n);
tn (n, 1,2,3);
}
void tn (int n, int i, int j, int w) /* рекурсивная */
{
if (n>1) /* функция */
{
tn (n_1, i, w, j);
tn (1, i, j, w);
tn (n_1, w, j, i);
}
else
printf (» \n % d ->%d», i, j);
return;
}
Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рис. 10. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.
Рис. 101. Стек Ханойских башен
В данной схеме круги - вызов функции tn, х - проверка условия выхода из рекурсии и печать перестановки на экран.
Во многих случаях рекурсивные функции можно заменить на эквивалентные нерекурсивные функции или фрагменты, используя стеки для хранения точек вызова и вспомогательных переменных.
2.6 Пример. (Функция Аккермана)
Вычислить функцию Аккермана, которая определяется так:
где N, X, Y - целые неотрицательные числа.
Следующая программа вычисляет функцию Аккермана с использованием рекурсивной функции ackr и вспомогательной функции smacc:
# include <stdio.h>
#include <conio.h>
int ackr (int, int, int);
main () /* вызывающая */
{
int x, y, n, t; /* функция */
scanf («%d % d % d»,&n,&x,&y);
t=ackr (n, x, y);
printf («%d», t);
}
int smacc (int n, int x) /* вспомогательная */
{
switch (n) /* функция */
{
case 0: return x+1;
case 1: return x;
case 2: return 0;
case 3: return 1;
default: return 2;
}
}
int ackr (int n, int x, int y) /* рекурсивная функция */
{
int z;
if (n==0 || y==0)
z=smacc (n, x);
else
{
z=ackr (n, x, y_1); /* рекурсивные */
z=ackr (n_1, z, x); /* вызовы ackr(…) */
}
return z;
}
2.7 Алгоритм быстрой сортировки (метод Хоора)
Метод «быстрой» сортировки, предложенный К. Хоором. основан на разделении массива на два непустых непересекающихся подмножества элементов. При этом в одной части массива должны оказаться все элементы, которые не превосходят по значению некоторый предварительно выбранный элемент массива, а в другой части - все элементы, не меньшие его. Аналогично следует поступить с каждой из полученных групп (при этом элемент для разделения можно выбирать просто из «середины» группы). Очевидно, что на определенном этапе массив окажется полностью отсортированным. В подавляющем большинстве реальных случаев использование «быстрой» сортировки дает лучшие результаты по времени, чем все прочие методы. Однако следует иметь в виду, что для нее нет гарантированной низкой трудоемкости вида O (n log n). где n - размер массива. Более того, иногда трудоемкость достигает величины O(n2) и не может быть снижена.
Исходя из этого, в особо критических ситуациях, когда результат должен выдаваться за жестко лимитированное время, применять «быструю» сортировку следует очень осмотрительно. Создатель языка Паскаль Н. Вирт сказал по поводу этого алгоритма следующее: «быстрая сортировка напоминает азартную игру, где следует заранее рассчитать, сколько можно позволить себе проиграть в случае невезения».
Программа использует рекурсивный вызов процедуры sortHoor для последовательного разделения массива. В качестве параметров процедуре передаются индексы начального и конечного элементов группы.
// Функция, реализующая метод Хоора
void sortHoor (int a[], int L, int R)
{
int i=L, j=R;
int x=a[(L+R) / 2];
while (i<=j)
{
while (a[i]<x)
i++;
while (a[j]>x)
j -;
if (i<=j)
{
swap (&a[i], &a[j]);
i++;
j - ;
}
}
if (L<j)
sortHoor (a, L, j);
if (i<R)
sortHoor (a, i, R);
}
3. Лабораторные задания
3.1 Сортировка массива рекурсивным способом
Напишите функцию, которая сортирует массив с использованием рекурсии.
3.2 Определитель матрицы
Найдите определитель матрицы рекурсивным способом.
3.3 Основная теорема арифметики
Найдите разложение натурального числа на простые множители с помощью рекурсии.
3.4 Распознавание формулы
Напишите функцию распознавания формулы, записанной в строке. Формула содержит: вещественные константы, переменную x и операции «+», «-», «*», «/».
4. Дополнительные задания
4.1 Корень уравнения
Написать функцию, которая находит корень уравнения рекурсивным способом методом дихотомии.
4.2 Лабиринт
Написать функции, которая находит выход из лабиринта
Библиографический список
1. Керниган Б. Язык программирования Си / Б. Керниган, Д. Ритчи. СПб.: Невский диалект, 2001. 352 с.
2. Подбельский В.В. Программирование на языке Си / В.В. Подбельский, С.С. Фомин. М.: Финансы и статистика, 2004. 600 с.
3. Программирование в Си. Организация ввода-вывода: метод. указания / сост. С.П. Трофимов. Екатеринбург: УГТУ, 1998. 14 с.
4. Программирование в Си. Динамическое распределение памяти: метод. указания / сост. С.П. Трофимов. Екатеринбург: УГТУ, 1998. 13 с.
Подобные документы
Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.
творческая работа [6,7 M], добавлен 01.02.2014Анализ и характеристика рекурсивного алгоритма решения задачи о Ханойских башнях, а также порядок его временной сложности в соответствии с пошаговым алгоритмом. Методика и особенности разработки программы, печатающей последовательность действий, ее текст.
курсовая работа [247,8 K], добавлен 08.02.2010Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Понятие стека как структуры данных, где элемент, занесенный первым, извлекается последним. Порядок добавления и удаления элементов списка. Реализация функций стека. Использование стека в алгоритме быстрой сортировки. Основные требования к элементам стека.
презентация [591,2 K], добавлен 22.10.2013Разработка программы, сортирующей массивы данных различного типа методом подсчета. Основные шаги алгоритма сортировки, ее свойства и модификация подсчетом. Целесообразность применения сортировки подсчетом. Условия эффективности алгоритма сортировки.
лабораторная работа [438,5 K], добавлен 16.07.2015Исторические предпосылки разработки тестирования. Виды электронных тестов и их роль в программировании. Этапы разработки программы для решения задачи быстрой сортировки. Пользовательский интерфейс, отладка, алгоритм программы. Файл теста в формате XML.
курсовая работа [1,5 M], добавлен 27.01.2014Организация вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Способы программирования алгоритмов с использованием рекурсии. Преимущества и недостатки использования рекурсии.
лабораторная работа [27,8 K], добавлен 28.05.2012Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Определение функции, ее прототип. Рекурсия - частичное определение объекта через себя. Рекурсивная функция произведения 2-х целых чисел. Задача о вычислении Факториала. Вычисление чисел Фибоначчи. Рекурсивное исполнение программы о Ханойских башнях.
презентация [1,2 M], добавлен 20.05.2012Литературный обзор методов распознавания кромок для схожих задач. Объекты в приложении и их отображение. Генерация выходных данных. Алгоритм распознавания линии (графика), отличный от градиентных подходов и использующий алгоритм предварительной обработки.
дипломная работа [711,8 K], добавлен 27.04.2014
