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

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

Возвращает наибольшее из двух целых: in t max( int a, in t b ) Возвращает наибольшее из трех целых: in t max( inta, intb, intс)

Возвращает наибольшее из первого параметра и длины второго: int max ( int a. string b )

Возвращает наибольшее из второго параметра и длины первого: int max ( string b, int a )

Console.WriteLineC max( 1, 2 ) ); Console.WriteLineC max( 1, 2. 3 ) ); Console.WriteLineC max( 1, 2 ) ): Console.WriteLineC max( 1 , 2 ) );

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

Если точного соответствия не найдено, выполняются неявные преобразования типов в соответствии с общими правилами, например, bool и char в int, float в double и т. п. Если преобразование невозможно, выдается сообщение об ошибке. Если соответствие на одном и том же этапе может быть получено более чем одним способом, выбирается лучший из вариантов, то есть вариант, содержащий меньшие количество и длину преобразований в соответствии с правилами, описанными в разделе Преобразования встроенных арифметических типов-значений (см. с. 45). Если существует несколько вариантов, из которых невозможно выбрать лучший, выдается сообщение об ошибке.

Вам уже известно, что все методы класса должны различаться сигнатурами. Это понятие было введено в разделе Методы (см. с. 106). Перегруженные методы имеют одно имя, но должны различаться параметрами, точнее, их типами и способами передачи (out или ref). Например, методы, заголовки которых приведены ниже, имеют различные сигнатуры и считаются перегруженными:

int maxC int a. int b )

in t max( inta, refintb)

Перегрузка методов является проявлением полиморфизма, одного из основных свойств ООП. Программисту гораздо удобнее помнить одно имя метода и использовать его для работы с различными типами данных, а решение о том, какой вариант метода вызвать, возложить на компилятор. Этот принцип широко используется в классах библиотеки .NET. Например, в стандартном классе Console метод WriteLine перегружен 19 раз для вывода величин разных типов.

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

Иногда бывает удобно создать метод, в который можно передавать разное количество аргументов. Язык С# предоставляет такую возможность с помощью ключевого слова params. Параметр, помеченный этим ключевым словом, размещается в списке параметров последним и обозначает массив заданного типа неопределенной длины, например:

public int Calculate( int a, out int c. params int[] d ) ...

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

его параметров, как и при вызове обычного метода, после чего управление передается первому исполняемому оператору метода. При повторном вызове этот процесс повторяется.

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

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

long facte long n ) {

if ( n == 0 11 n == 1 ) return 1; нерекурсивная ветвь

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

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

long factt long n ) {

return ( n >1 ) ? n *facte n -1 ) : 1:

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

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

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

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

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

smespace ConsoleApplicationi class Classl

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!)

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

Console.WriteLine! Average! a ) ); III

intC] b = { -11. -4, 12, 14, 32, -1, 28 }; Console.WriteLine! Average! b ) ); /12

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;

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

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

ПРИМЕЧАНИЕ

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