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

Кафедра: Автоматика и Информационные Технологии

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

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)

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 с.