Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.1. Печать в обратном порядке 
static void Invert() 
{ 
Char ch = Convert.ToChar(Console.Read()); 
if (ch != '.') 
Invert(); 
Console.Write(ch); 
} 
Работа функции
Invert
() для входной последовательности 'a' 'b' 'c' '.' 
показана на рисунке 3.1. 
При каждом вызове функции Invert()
выделяется место под локаль-
ную переменную ch, значения которой приведены в правом верхнем углу 
программного текста. Стрелками с цифрами в кружках обозначены рекур-
сивные вызовы (1, 2, 3). Стрелка (4) показывает работу функции в том слу-
чае, когда условие рекурсивного обращения к функции не выполняется. Воз-
враты к предыдущему вызову обозначены стрелками (5, 6, 7). Стрелка (8) 
обозначает возврат в вызывающую программу при полном завершении рабо-
ты функции. 
2 / 23

---

49 
Рис
. 3.1. 
Последовательн
ост
ь 
реку
рси
вн
ы
х 
вы
зов
ов
процедур
ы
Inve
rt()
4
8
ch =
‘a
’; 
if(ch
!=
'.
')
I
nve
rt(
);
Con-
ch = 
‘b’; 
if(c
h !
=
'.') 
I
nve
rt(
);
ch =
‘c
’; 
if(c
h !
=
'.') 
I
nve
rt(
);
ch =
‘.
’; 
if(c
h !
=
'.') 
I
nve
rt(
);
1
2
3
“
“.c” 
5
6
7
‘c’ 
‘b
’ 
‘a’ 
‘.’ 
“.” 
“.cba” 
49 
3 / 23

---

50 
3.2. К
ОГДА РЕКУРСИЯ НЕОБХОДИМА
 
Далеко не всегда рекурсия бывает необходимой. Напомним, что при 
каждом рекурсивном вызове функции выделяется память для размещения ее 
переменных. Кроме этих локальных переменных нужно еще сохранять теку-
щее состояние вычислений, чтобы вернуться к нему, когда закончится вы-
полнение новой активации функции и нужно будет вернуться к старой. Все 
эти данные, а также и адрес возврата операционная система помещает в сис-
темный стек. Эти накладные расходы необходимо учитывать при выборе ме-
жду рекурсивным и нерекурсивным решением. 
Для примера рассмотрим рекурсивную функцию вычисления факто-
риала. Определение факториала по своей сути является рекурсивным, и, ка-
залось бы, алгоритм его вычисления тоже должен быть таким же. Приведен-
ная ниже функция Factorial является калькой определения: 
Листинг 3.2. Вычисление факториала. Вариант 1 
static int Factorial(int k) 
{
int result; 
if (k == 1) 
result = 1; 
else 
result = k * Factorial(k-1); 
return result; 
} 
Однако итеративный алгоритм вычисления факториала нисколько не 
сложнее, и к тому же лишен накладных расходов, связанных с рекурсией: 
Листинг 3.3. Вычисление факториала. Вариант 2 
static int FactorialI(int k) 
{ 
int result = 1; 
for (int i = 1; i <= k; i++) 
result *= i; 
return result; 
} 
4 / 23

---

51 
На ряде других аналогичных примеров можно показать, что если име-
ется очевидное итеративное решение задачи, то следует избегать рекурсии. 
Любую рекурсивную программу можно преобразовать в чисто итера-
тивную. Но для этого придется самим создавать стек для рекурсивных вызо-
вов и оперировать с ним, и порой эти операции до такой степени заслоняют 
основной алгоритм, что понять его становится весьма и весьма трудно. По-
этому алгоритмы, которые по своей природе скорее рекурсивны, чем итера-
тивны, следует представлять в виде рекурсивных процедур.