Когда рекурсия не нужна

При новом рекурсивном вызове компьютер делает так:

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 уровнейрекурсии).