Контрольная работа по предмету "Программирование, компьютеры и кибернетика, ИТ технологии"

Узнать цену работы по вашей теме


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



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

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

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)] =



Не сдавайте скачаную работу преподавателю!
Данную контрольную работу Вы можете использовать для выполнения своих заданий.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :