Рекурсивные функции
Основные понятия рекурсии
Классификация рекурсивных функций
Определение. Рекурсивной называют функцию, которая прямо или косвенно сама вызывает себя.
Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна.
Если в теле функции явно используется вызов этой же функции, то имеет место прямая рекурсия.
Рекурсия называется однократной, если функция вызывает саму себя один раз. Если функция вызывает саму себя два раза, то рекурсия называется двукратной и т.д.
Стек рекурсивных функций
При каждом обращении к рекурсивной функции в стеке выделяется место для:
- адреса возврата в вызывающую функцию и вершины стека вызывающей функции (4 байта),
- списка фактических параметров (может быть пустым),
- локальных переменных рекурсивной функции (могут отсутствовать).
Определение. Схемой стека вызовов функций называется последовательность экземпляров функций, вызывающих друг друга.
Для просмотра стека вызовов Borland C++ существует команда отладчика Debug – Call Stack… (Ctrl + F3). В служебном окне выводится список функций, начинающийся с main, которые вызывают друг друга на каждом шаге отладки.
Мы будем использовать другое графическое представление схемы стека вызовов.
Примеры стека функций
Пример 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.
Примеры рекурсивных функций
Пример. (Однократная явная рекурсия)
Вычислить 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. Схема стека вызовов