Рекурсивные методы. 
Программирование. 
Базовый курс с#

Рекурсивным называют метод, который прямо (непосредственно) или косвенно вызывает самого себя. Метод называют косвенно рекурсивным, если он содержит обращение к другому методу, содержащему прямой или косвенный вызов определяемого (первого) метода. В случае косвенной рекурсивности по тексту определения метода его рекурсивность может быть не видна. Если в теле метода явно используется обращение к этому методу, то имеет место прямая рекурсия. В этом случае говорят, что метод самовызывающий (self-calling). Именно самовызывающие методы будем называть рекурсивными, а для методов с косвенной рекурсией будем использовать термин «косвенно рекурсивные методы».

Классический пример рекурсивного метода — функция для вычисления факториала неотрицательного целого числа. На языке C# ее можно записать таким образом:

static long fact (int k).

{

if (k < 0) return 0;

if (к == 0 || к == 1) return 1; return к * fact (k — 1);

}

Для отрицательного аргумента результат (по определению факториала) не существует. В этом случае функция возвращает нулевое значение (можно было бы возвращать, например, отрицательное значение). Для нулевого и единичного аргумента, по определению факториала, возвращаемое значение равно 1. Если k > 1, то вызывается та же функция с уменьшенным на 1 значением аргумента и возвращаемое ею значение умножается на текущее значение аргумента к. Тем самым организуется вычисление произведения 1*2*3*…* (к-2)* (к — 1) * к.

При проектировании рекурсивного метода нужно убедиться:

• — что он может завершить работу, т. е. невозможно возникновение зацикливания;
• — что метод приводит к получению правильных результатов.

Для удовлетворения первого требования должны соблюдаться два правила:

• 1) в последовательности рекурсивных вызовов должен быть явный разрыв, т. е. самовызовы должны выполняться до тех пор, пока истинно значение некоторого выражения, операнды которого изменяются от вызова к вызову;
• 2) при самовызовах должны происходить изменения параметров и эти изменения после конечного числа вызовов должны привести к нарушению проверяемого условия из пункта 1.

В нашем примере условием выхода из цепочки рекурсивных вызовов является истинность выражения (k == 0| |к == 1). Так как значение к конечно и параметр при каждом следующем вызове уменьшается на 1, то цепочка самовызовов конечна. Идя от конца цепочки, т. е. от 1 ! = 1, к началу, можно убедиться, что все вызовы работают верно и метод работает правильно.

Иллюстрация цепочки самовызовов для метода вычисления факториала:

Эффективность рекурсивного метода зачастую определяется глубиной рекурсии, т. е. количеством самовызовов в одной цепочке при обращении к методу.

В качестве еще одного примера рекурсии приведем метод, преобразующий все цифры натурального числа в соответствующие им символы. Параметр метода — целое число типа int, результат — массив char[]. Код метода:

// Цифры натурального числа: static char[] arNumbs (int n).

{

if (n / 10 == 0).

{ return new char[] { (char)(n + (int)'0') }; }.

else.

{

char[] res = arNumbs (n / 10); int L = res. Length;

Array.Resize (ref res, L + 1); res[L] = (char)((n % 10) + (int)'0‘); return res;

} }

В коде метода arNumbs (int n) первый шаг — проверка результата целочисленного деления значения параметра на 10. Если результат нулевой, то значение параметра — число меньшее 10 и представлено одной цифрой. В этом случае в операторе возврата из метода создается символьный массив из одного элемента со значением, равным символьному представлению значения параметра (одной цифры). Ссылка на массив из одного элемента — это результат, возвращаемый методом при прерывании цепочки рекурсивных самовызовов.

В более общем случае параметр больше 10 и выполняется блок операторов, размещенных в ветви else. Объявляется ссылка char [] res, которой присваивается результат рекурсивного обращения к методу arNumbs (n/10). Для полученного из этого метода массива вычисляется размер (свойство res. Length). Затем метод Array. ResizeO увеличивает на 1 размер массива, связанного со ссылкой res. В последний элемент нового массива заносится символьное представление последней цифры значения параметра. Ссылка на полученный массив возвращается как результат рекурсивного вызова.

Для иллюстрации выполнения метода используем следующий код:

static void MainQ.

{

foreach (var c in arNumbs (90 580)).

Console.Write (c + ««);

}

Результат выполнения программы:

9 0 5 8 0.

Цепочка рекурсивных вызовов для приведенного кода:

arNumbs (90 580) -> arNumbs (9 058) -> arNumbs (905) -> arNumbs (0090) -> arNumbs (009) -> разрыв цепочки.

Цепочка возвратов из самовызовов:

res[0] = '9' -> res[l] = '0' -> res[2] = '5' -> res[3] = '8' -> res[4] = '0'.

Многие задачи, требующие циклического повторения операций, могут быть представлены как рекурсивными, так и итерационными алгоритмами. Основной для рекурсивного алгоритма является его самовызов, а для итерационного алгоритма — цикл.

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

Параметры метода — ссылка на одномерный символьный массив и индекс первого выводимого элемента. Окончание вывода — конец массива либо терминальный символ '' в качестве значения очередного элемента.

// Рекурсивный метод печати элементов символьного массива static void chPrint (char[] ch, int beg).

{

if (beg >= ch. Length-1 || ch[beg] == '').

{

Console.WriteLine (); return;

}

Console.Write (ch[beg] + ««);

chPrint (ch, beg + 1);

}

Первый параметр метода char[] ch — ссылка на обрабатываемый символьный массив. Второй параметр int beg — индекс элемента, начиная с которого выводятся значения. Условие выхода из метода — достижение конца массива beg > = ch. Length-1 или значение '' элемента с индексом beg. Если условие выхода не достигнуто, выполняются операторы:

Console.Write (ch[beg] + ««); chPrint (ch, beg + 1);

Тем самым первым выводится значение начального элемента массива и происходит самовызов метода для следующего значения второго параметра, и т. д…

Вызов последнего отличного от '' элемента или достижение конца массива завершает цепочку рекурсивных обращений.

Пример использования приведенного метода (09₁₇.cs):

static void MainQ.

{

int size = 9;

char[] simbols = new char[size];

string line = «AaBbCc» ;

for (int к = 0; к < line. Length; k++) simbols[k] = line[k]; chPrint (simbols, 0);

}

Результат выполнения программы:

A a в b С с Обратите внимание, что при обращении к методу chPrint () второй аргумент равен 0, т. е. вывод идет с начала массива.