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

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

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

В качестве демонстрации рекурсивной функции обычно приводят пример вычисления факториала числа N, исходя из того, что 0!=1 и 1!=1, а N!=N*(N-1). Выглядит это так:

#include <iostream.h> long factorial (long a){ if (a > 1) return (a * factorial (a-1)); else return (1);} int main (){ long l; cout << "Type a number: "; cin >> l; cout << "!" << l << " = " << factorial (l); return 0;}

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

Часто используют такую форму рекурсивной функции (в нашем случае имеющей возвращаемый тип void):

void recurs(argumentlist){ statements1 if (test) recurs(arguments) statements2} Предполагается, что test когда-нибудь будет равно false, и цепь вызовов прервется.Для иллюстрации такого поведения рекурсии приведем пример (“countdown” – обратный отсчет): // recur.cpp – использование рекурсии#include <iostream>using namespace std;void countdown(int n); int main(){ countdown(4); // вызов рекурсивной ф-ии return 0;}void countdown(int n){ cout << "Counting down... " << n << "\n"; if (n > 0) countdown(n-1); // функция вызывает сама себя cout << n << ": Boom!\n";} Результат: Counting down... 4 уровень 1; продвижение по уровням рекурсииCounting down... 3 уровень 2Counting down... 2 уровень 3Counting down... 1 уровень 4Counting down... 0 уровень 5; последний рекурсивный вызов 0: Boom! уровень 5; начало обратного хода1: Boom! уровень 42: Boom! уровень 33: Boom! уровень 24: Boom! уровень 1 Заметим, что при каждом рекурсивном вызове создается свой собственный набор переменных, так что ко времени достижения пятого вызова, программа будет иметь пять отдельных переменных с именем n, каждая из которых имеет свое значение.

Перегруженные функции (полиморфизм функций)

Напомним (см. пред. Лекцию) еще раз механизм перегрузки…

Перегруженная (иногда говорят – “ перегружаемая”) функция выполняет различные действия в зависимости от типов данных, передаваемых ей в качестве аргументов. По сути, перегрузка функций – это совместное использование (sharing) несколькими функциями одного и того же имени. В этом контексте часто говорят о полиморфизме функций в C++. Полиморфная функция имеет несколько вариантов исполнения.

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

#include <iostream.h>

int square(int i)

{ return i * i; }

float square(float f)

{ return f * f; }

int main()

{

int a = 2;

float b = 0.5;

cout << "The square of " << a << " is " << square(a) << endl;

cout << "The square of " << b << " is " << square(b) << endl;

return 0;

}

На выходе программы получим:

Дата добавления: 2015-11-16