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

Г
ЛАВА 
3. Р
ЕКУРСИЯ 
 
Рекурсия относится к числу фундаментальных понятий математики и 
информатики. В математике рекурсивной называют функцию, в определении 
которой содержится сама эта функция. Часто это функции целочисленного 
аргумента, которые задаются с помощью рекуррентных отношений. Приме-
рами таких отношений являются определения функции факториала: 
(
)
!
1 ! , 0! 1
n
n n
=
−
=
и числовой последовательности Фибоначчи: 
( )
(
)
(
) ( )
( )
1
2 ,
0
1
1
F n
F n
F n
F
F
=
− +
−
=
= . 
В математике широко используются рекурсивные определения матема-
тических объектов. В качестве примера можно привести рекурсивное опре-
деление натурального числа: 
− 1 есть натуральное число; 
− целое число, следующее за натуральным, есть натуральное число. 
3.1. Р
ЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ И РЕКУРСИВНЫЕ АЛГО-
РИТМЫ
 
Мощность рекурсии определяется тем, что она позволяет определить 
бесконечное множество объектов с помощью конечного высказывания. 
В частности рекурсивные определения широко используются для описания 
языков программирования. Например, в языке C# оператор — это и заклю-
ченная в операторные скобки { и } последовательность операторов, и опера-
тор цикла, телом которого также является оператор. Благодаря рекурсивным 
определениям и существует все бесконечное разнообразие программ. 
В программировании рекурсивными могут быть как структуры данных, 
так и алгоритмы. Характерной рекурсивной структурой являются деревья, 
которые будут рассматриваться в следующей главе. 
Бесконечные вычисления можно описать с помощью конечной рекур-
сивной программы, даже если эта программа не содержит явных циклов. Не-
обходимое и достаточное средство для рекурсивного задания алгоритмов – 
это представление их в виде функций, содержащих в своем теле вызовы са-
мих себя. Это называется прямой рекурсией. Если функция P содержит обра-
щение к функции Q, которая содержит обращение к P, то функция P называ-
ется косвенно рекурсивной. 
23 / 23

---

47 
Любая функция, вообще говоря, содержит некоторое множество ло-
кальных объектов, т.е. объектов, которые определены в самой этой функции. 
Когда функция вызывает сама себя, то для всех ее локальных переменных 
выделяется новая память в системном стеке, и вложенный вызов работает с 
собственным представлением локальных переменных. Когда вложенный вы-
зов завершается, занимаемая его переменными область памяти в стеке осво-
бождается и актуальным становится представление локальных переменных 
предыдущего уровня.
Хотя локальные переменные имеют те же имена, что и 
соответствующие переменные, созданные при предыдущем вызове этой же 
процедуры, их значения различны. Это обусловлено тем, что при работе про-
цедуры используются переменные, созданные последними. Это же относится 
и к параметрам функции. 
Рекурсивные функции могут привести к бесконечным вычислениям. При 
написании рекурсивной программы следует позаботиться о том, чтобы ее ра-
бота когда-либо завершилась. Для этого необходимо, чтобы рекурсивное об-
ращение к функции P подчинялось некоторому условию C, которое в какой-то 
момент перестанет выполняться. Завершение рекурсии хорошо видно в опре-
делении факториала: при n = 1 факториал вычисляется непосредственно.
Следовательно, рекурсивная функция P должна иметь вид: 
if (C)
P;
// 
рекурсивный вызов 
else T; // 
непосредственное вычисление или дейст-
вие 
или 
 
while (C)
P; // 
рекурсивный вызов 
T; // 
непосредственное вычисление или дейст-
вие 
или некоторую другую эквивалентную форму. 
В ряде случаях завершением выполнения соответствующей функции 
может управлять некоторая связанная с этой функцией величина N, то есть 
целое неотрицательное число, относительно которого можно было бы с уве-
ренностью сказать, что оно убывает при каждом рекурсивном вызове функ-
ции. В простейшем случае роль такой управляющей величины может играть 
один из параметров функции. И тогда любая функция, построенная по сле-
дующей схеме: 
void P(int N, …); 
{ 
1 / 23

---

48 
if (N == 0) 
T; // 
непосредственное вычисление или 
действие 
else
P(N-1, …); // 
рекурсивный вызов с параметром,
// 
на единицу меньшим 
} 
после конечного числа рекурсивных вызовов выдаст определенный результат 
для каждого неотрицательного N. 
В качестве примера рассмотрим функцию, которая читает последова-
тельность символов, завершающуюся точкой, и выводит ее в инвертирован-
ном виде.