При новом рекурсивном вызове компьютер делает так:
1. Запоминается состояние вычислений на данном этапе.
2. В стеке (особой области памяти) создается новый набор локальных переменных (чтобы
не испортить переменные текущего вызова).
Поскольку при каждом вызове затрачивается новая память и расходуется время на вызов процедуры и возврат из нее, при использовании рекурсии необходимо помнить, что
глубина рекурсии (количество вложенных вызовов) должна была достаточно мала.
Программа, использующая рекурсию с большой глубиной, будет выполняться долго и может вызвать переполнение стека (нехватку стековой памяти). Поэтому
если задача может быть легко решена без использования рекурсии, рекурсию использовать нежелательно.
Например, задача вычисления факториала очень просто решается с помощью обычного цикла
for (такое решение с помощью циклов называют итеративным, циклическим):
Int Factorial (int n)
{
int i, fact = 1;
for (i = 2; i <= n; i ++)
fact *= i;
return fact;
}
Эта функция работает намного быстрее, чем рекурсивная.
|
|
Доказано, что любая рекурсивная программа может быть написана без использования рекурсии, хотя такая реализация может оказаться очень сложной.
Задача. Составить функцию для вычисления чисел Фибоначчи fi, которые задаются так:
1. f0= 0, f1 = 1.
2. fi= fi-1 + fi-2 для i > 1.
Использование рекурсии «в лоб» дает функцию
Int Fib (int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return Fib(n-1) + Fib(n-2);
}
Заметим, что каждый рекурсивный вызов при n > 1 порождает еще 2 вызова функции, многие выражения (числа Фибоначчи для малых n) вычисляются много раз. Поэтому практического значения этот алгоритм не имеет, особенно для больших n. Схема вычисления Fib(5) показана в виде дерева ниже:
Заметим, что очередное число Фибоначчи зависит только от двух предыдущих, которые будем хранить в переменных f1 и f2. Сначала примем f1=1 и f2=0, затем вычисляем следующее число Фибоначчи и записываем его в переменную x. Теперь значение f2 уже не нужно и мы скопируем f1 в f2 и x в f1.
Int Fib2(int n)
{
int i, f1 = 1, f2 = 0, x;
for (i = 2; i <= n; i ++) {
x = f1 + f2; // следующеечисло
f2 = f1; f1 = x; // сдвиг значений
}
return x;
}
Такая процедура для больших n (>20) работает в сотни тысяч (!!!) раз быстрее, чем рекурсивная. Вывод: там, где можно легко обойтись без рекурсии, надо без нее обходиться.
Рекурсивный поиск
Вспомним задачу, которая рассматривалась при обсуждении работы со строками: опреде-
лить, сколько раз встречается заданное слово в предложении. Рекурсивную процедуру можно описать так:
1) ищем первое заданное слово с помощью функции strstr; если не нашли, то стоп;
2) количество слов = 1 + количество слов в оставшейся части строки.
|
|
int HowMany(char *s, char *word)
{
char *p = strstr(s, word); // ищемпервоеслово
if (! p) return 0; // ненашли – 0 слов
return 1 + // одноуженашли,...
HowMany(p+strlen(word),word); // ищемдальше
}
Функция получилась короткая, понятная, но по скорости работы не самая эффективная.
Рекурсивные фигуры
Многие рисунки и кривые задаются рекурсивно. Рассмотрим сначала простейший пример. В центре рисунка – большая окружность. На ней находятся центры четырех окружностей меньшего диаметра, на каждой из которых – центры еще четырех окружно-
стей еще меньшего диаметра и т.д. Всего – N разных диаметров (N уровнейрекурсии).