Рекурсивные методы

Рекурсивным называется метод, который вызывает сам себя. Такая рекурсия назы­вается прямой. Существует еще косвенная рекурсия, когда два или более метода вызывают друг друга. Если метод вызывает себя, в стеке создается копия значений его параметров, как и при вызове обычного метода, после чего управление пере­дается первому исполняемому оператору метода. При повторном вызове этот процесс повторяется.

Ясно, что для завершения вычислений каждый рекурсивный метод должен содер­жать хотя бы одну нерекурсивную ветвь алгоритма, заканчивающуюся оператором возврата. При завершении метода соответствующая часть стека освобождается и управление передается вызывающему методу, выполнение которого продолжа­ется с точки, следующей за рекурсивным вызовом.

Классическим примером рекурсивной функции является функция вычисления факториала (это не означает, что факториал следует вычислять именно так). Для! того чтобы получить значение факториала числа п, требуется умножить на п фак­ториал числа (п - 1). Известно также, что 0!= 1 и 1!= 1:

long fact(long n)

{

if (n == 0 || n == 1)

return 1; // нерекурсивная ветвь

return (n * fact(n - 1)); // рекурсивная ветвь

}

To же самое можно записать короче:

long fact(long n)

{

return (n > 1)? n * fact(n - 1): 1;

}

Рекурсивные методы чаще всего применяют для компактной реализации рекур­сивных алгоритмов, а также для работы со структурами данных, описанными ре­курсивно, например, с двоичными деревьями (понятие о двоичном дереве дается в главе 13). Любой рекурсивный метод можно реализовать без применения ре­курсии, для этого программист должен обеспечить хранение всех необходимых данных самостоятельно.

К достоинствам рекурсии можно отнести компактность записи, к недостат­кам — расход времени и памяти на повторные вызовы метода и передачу ему ко­пий параметров, а главное, опасность переполнения стека.

Методы с переменным количеством аргументов

Иногда бывает удобно создать метод, в который можно передавать разное ко­личество аргументов. Язык С# предоставляет такую возможность с помощью ключевого слова params. Параметр, помеченный этим ключевым словом, раз­мещается в списке параметров последним и обозначает массив заданного типа неопределенной длины, например: public int Calculate(int a. out int с params int[] d)...

В этот метод можно передать три и более параметров. Внутри метода к параметрам начиная с третьего, обращаются как к обычным элементам массива. Количество

элементов массива получают с помощью его свойства Length. В качестве примера рассмотрим метод вычисления среднего значения элементов массива (листинг 7.1).

Листинг 7.1. Метод с переменным числом параметров

using System;

namespace ConsoleApplication1

{

class Class1

{

public static double Average(params int[] a)

{

if (a.Length == 0)

throw new Exception("Недостаточно аргументов в методе");

double av = 0;

foreach (int elem in a)

av += elem;

return av / a.Length;

}

static void Main()

{

try

{

int[] a = { 10, 20, 30 };

Console.WriteLine(Average(a)); // 1

int[] b = { -11, -4, 12, 14, 32, -1, 28 };

Console.WriteLine(Average(b)); // 2

short z = 1.e - 12;

byte v = 100;

Console.WriteLine(Average(z, e, v)); // 3

Console.WriteLine(Average()); // 4

}

catch (Exception e)

{

Console.WriteLine(e.Message);

return;

}

}

}

}

Результат работы программы:

10 20 40

Недостаточно аргументов в методе

ПРИМЕЧАНИЕ

В данном алгоритме отсутствие аргументов при вызове метода Average является ошибкой. Этот случай обрабатывается генерацией исключения. Если не обработать эту ошибку, результат вычисления среднего будет равен «не числу» (NaN) вследст­вие деления на ноль в операторе возврата из метода.

Параметр-массив может быть только один и должен располагаться последним в списке. Соответствующие ему аргументы должны иметь типы, для которых воз­можно неявное преобразование к типу массива.