Метасимволы в регулярных выражениях

Регулярное выражение – это шаблон, по которому выполняется поиск соответствующего фрагмента текста. Язык описания регулярных выражений состоит из символов двух видов: обычных символов и метасимволов. Обычный символ представляет в выражении сам себя, а метасимвол – некоторый класс символов.

Рассмотрим наиболее употребительные метасимволы:

Класс символов	Описание	Пример
.	Любой символ, кроме \n.	Выражение c.t соответствует фрагментам: cat, cut, c#t, c{t и т.д.
[]	Любой одиночный символ из последовательности, записанной внутри скобок. Допускается использование диапазонов символов.	Выражение c[aui]t соответствует фрагментам: cat, cut, cit. Выражение c[a-c]t соответствует фрагментам: cat, cbt, cct.
[^]	Любой одиночный символ, не входящий в последовательность, записанную внутри скобок. Допускается использование диапазонов символов.	Выражение c[^aui]t соответствует фрагментам: cbt, cct, c2t и т.д. Выражение c[^a-c]t соответствует фрагментам: cdt, cet, c%t и т.д.
\w	Любой алфавитно-цифровой символ.	Выражение c\wt соответствует фрагментам: cbt, cct, c2t и т.д., но не соответствует фрагментам c%t, c{t и т.д.
\W	Любой не алфавитно-цифровой символ.	Выражение c\Wt соответствует фрагментам: c%t, c{t, c.t и т.д., но не соответствует фрагментам cbt, cct, c2t и т.д.
\s	Любой пробельный символ.	Выражение \s\w\w\w\s соответствует любому слову из трех букв, окруженному пробельными символами.
\S	Любой не пробельный символ.	Выражение \s\S\S\S\s соответствует любым трем непробельным символам, окруженным пробельными.
\d	Любая десятичная цифра	Выражение c\dt соответствует фрагментам: c1t, c2t, c3t и т.д.
\D	Любой символ, не являющийся десятичной цифрой	Выражение c\Dt не соответствует фрагментам: c1t, c2t, c3t и т.д.

Кроме метасимволов, обозначающие классы символов, могут применяться уточняющие метасимволы:

Уточняющие символы	Описание
^	Фрагмент, совпадающий с регулярными выражениями, следует искать только в начале строки
$	Фрагмент, совпадающий с регулярными выражениями, следует искать только в конце строки
\А	Фрагмент, совпадающий с регулярными выражениями, следует искать только в начале многострочной строки
\Z	Фрагмент, совпадающий с регулярными выражениями, следует искать только в конце многострочной строки
\b	Фрагмент, совпадающий с регулярными выражениями, начинается или заканчивается на границе слова, т.е. между символами, соответствующими метасимволам \w и \W
\B	Фрагмент, совпадающий с регулярными выражениями, не должен встречаться на границе слов

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

Повторители	Описание	Пример
*	Ноль или более повторений предыдущего элемента	Выражение ca*t соответствует фрагментам: ct, cat, caat, caaat и т.д.
+	Одно или более повторений предыдущего элемента	Выражение ca+t соответствует фрагментам: cat, caat, caaat и т.д.
?	Не более одного повторения предыдущего элемента	Выражение ca?t соответствует фрагментам: ct, cat.
{n}	Ровно n повторений предыдущего элемента	Выражение ca{3}t соответствует фрагменту: cаааt. Выражение (cat){2} соответствует фрагменту: cаtcat.
{n,}	По крайней мере n повторений предыдущего элемента	Выражение ca{3,}t соответствует фрагментам: cаааt, caaaat, caaaaaaat и т.д. Выражение (cat){2,} соответствует фрагментам: cаtcat, catcatcat и т.д.
{n, m}	От n до m повторений предыдущего элемента	Выражение ca{2, 4}t соответствует фрагментам: cааt, caaat, caaaat.

Регулярное выражение записывается в виде строкового литерала, причем перед строкой необходимо ставить символ @, который говорит о том, что строку нужно будет рассматривать и в том случае, если она будет занимать несколько строчек на экране. Однако символ @ можно не ставить, если в качестве шаблона используется шаблон без метасимволов.

Замечание. Если нужно найти какой-то символ, который является метасимволом, например, точку, можно это сделать защитив ее обратным слэшем. Т.е. просто точка означает любой одиночный символ, а \. означает просто точку.

Примеры регулярных выражений:

· слово rus – @"rus" или "rus"

· номер телефона в формате xxx-xx-xx – @"\d\d\d-\d\d-\d\d" или @"\d{3}(-\d\d){2}"

· номер автомобиля - @"[A-Z]\d{3}[A-Z]{2}\d{2,3}RUS"

Задания. Запишите регулярное выражение, соответствующее:

1. дате в формате дд.мм.гг или дд.мм.гггг

2. времени в формате чч.мм или чч:мм

3. целому числу (со знаком и без)

4. вещественному числу (со знаком и без, с дробной частью и без, с целой частью и без)

Поиск в тексте по шаблону

Пространство имен библиотеки базовых классов System.Text.RegularExpressions содержит все объекты платформы .NET Framework, имеющие отношение к регулярным выражениям. Важнейшим классом, поддерживающим регулярные выражения, является класс Regex, который представляет неизменяемые откомпилированные регулярные выражения. Для описания регулярного выражения в классе определено несколько перегруженных конструкторов:

3) Regex() – создает пустое выражение;

4) Regex(String) – создает заданное выражение;

5) Regex(String, RegexOptions) – создает заданное выражение и задает параметры для его обработки с помощью элементов перечисления RegexOptions (например, различать или нет прописные и строчные буквы).

Поиск фрагментов строки, соответствующих заданному выражению, выполняется с помощью методов IsMach, Mach, Matches класса Regex.

Метод IsMach возвращает true, если фрагмент, соответствующий выражению, в заданной строке найден, и false в противном случае. Например, попытаемся определить, встречается ли в заданном тексте слово собака:

static void Main()

{

Regex r = new Regex("собака",RegexOptions.IgnoreCase);

string text1 = "Кот в доме, собака в конуре.";

string text2 = "Котик в доме, собачка в конуре.";

Console.WriteLine(r.IsMatch(text1));

Console.WriteLine(r.IsMatch(text2));

}

Замечание. RegexOptions.IgnoreCase – означает, что регулярное выражение применяется без учеба регистра символов

Можно использовать конструкцию выбора из нескольких элементов. Варианты выбора перечисляются через вертикальную черту. Например, попытаемся определить, встречается ли в заданном тексте слов собака или кот:

static void Main(string[] args)

{

Regex r = new Regex("собака|кот",RegexOptions.IgnoreCase);

string text1 = "Кот в доме, собака в конуре.";

string text2 = "Котик в доме, собачка в конуре.";

Console.WriteLine(r.IsMatch(text1));

Console.WriteLine(r.IsMatch(text2));

}

Попытаемся определить, есть ли в заданных строках номера телефона в формате xx-xx-xx или xxx-xx-xx:

static void Main()

{

Regex r = new Regex(@"\d{2,3}(-\d\d){2}");

string text1 = "tel:123-45-67";

string text2 = "tel:no";

string text3 = "tel:12-34-56";

Console.WriteLine(r.IsMatch(text1));

Console.WriteLine(r.IsMatch(text2));

Console.WriteLine(r.IsMatch(text3));

}

Задание. Измените программу так, чтобы можно было определить, содержится в тексте дата в формате дд.мм.гг.

Метод Match класса Regex не просто определяет, содержится ли текст, соответствующий шаблону, а возвращает объект класса Match – последовательность фрагментов текста, совпавших с шаблоном. Следующий пример позволяет найти все номера телефонов в указанном фрагменте текста:

static void Main()

{

Regex r = new Regex(@"\d{2,3}(-\d\d){2}");

string text = @"Контакты в Москве tel:123-45-67, 123-34-56; fax:123-56-45

Контакты в Саратове tel:12-34-56; fax:12-56-45";

Match tel = r.Match(text);

while (tel.Success)

{

Console.WriteLine(tel);

tel = tel.NextMatch();

}

}

Следующий пример позволяет подсчитать сумму целых чисел, встречающихся в тексте:

static void Main()

{

Regex r = new Regex(@"[-+]?\d+");

string text = @"5*10=50 -80/40=-2";

Match teg = r.Match(text);

int sum = 0;

while (teg.Success)

{

Console.WriteLine(teg);

sum += int.Parse(teg.ToString());

teg = teg.NextMatch();

}

Console.WriteLine("sum=" + sum);

}

Задание. Измените программу так, чтобы на экран дополнительно выводилось количество найденных чисел.

Метод Matchesкласса Regex возвращает объект класса MatchCollection – коллекцию всех фрагментов заданной строки, совпавших с шаблоном. При этом метод Matches многократно запускает метод Match, каждый раз начиная поиск с того места, на котором закончился предыдущий поиск.

static void Main(string[] args)

{

string text = @"5*10=50 -80/40=-2";

Regex theReg = new Regex(@"[-+]?\d+");

MatchCollection theMatches = theReg.Matches(text);

foreach (Match theMatch in theMatches)

{

Console.Write("{0} ", theMatch.ToString());

}

Console.WriteLine();

}

}

Редактирование текста

Регулярные выражения могут эффективно использоваться для редактирования текста. Например, метод Replace класса Regex позволяет выполнять замену одного фрагмента текста другим или удаление фрагментов текста:

Пример 1. Изменение номеров телефонов:

static void Main(string[] args)

{

string text = @"Контакты в Москве tel:123-45-67, 123-34-56; fax:123-56-45.

Контакты в Саратове tel:12-34-56; fax:11-56-45";

Console.WriteLine("Старые данные\n"+text);

string newText=Regex.Replace(text, "123-", "890-");

Console.WriteLine("Новые данные\n" + newText);

}

Задание. Измените программу так, чтобы шестизначные номера заменялись на семизначные добавлением 0 после первых двух цифр. Например, номер 12-34-56 заменился бы на 120-34-56.

Пример 2. Удаление всех номеров телефонов из текста:

static void Main()

{

string text = @"Контакты в Москве tel:123-45-67, 123-34-56; fax:123-56-45.

Контакты в Саратове tel:12-34-56; fax:12-56-45";

Console.WriteLine("Старые данные\n"+text);

string newText=Regex.Replace(text, @"\d{2,3}(-\d\d){2}", "");

Console.WriteLine("Новые данные\n" + newText);

}

}

Задание. Измените программу так, чтобы из текста удалялись слова tel и fax (если после данных слов стоят двоеточия, то их тоже следует удалить).

Пример 3. Разбиение исходного текста на фрагменты:

static void Main()

{

string text = @"Контакты в Москве tel:123-45-67, 123-34-56; fax:123-56-45.

Контакты в Саратове tel:12-34-56; fax:12-56-45";

string []newText=Regex.Split(text,"[ ,.:;]+");

foreach( string a in newText)

Console.WriteLine(a);

}

Задание. Разместите текст на одной строке и посмотрите, как изменится вывод данных. Объясните результаты.

Методы: основные понятия

Метод – это функциональный элемент класса, который реализует вычисления или другие действия, выполняемые классом или его экземпляром (объектом). Метод представляет собой законченный фрагмент кода, к которому можно обратиться по имени. Он описывается один раз, а вызываться может многократно. Совокупность методов класса определяет, что конкретно может делать класс. Например, стандартный класс Math содержит методы, которые позволяют вычислять значения математический функций.

Синтаксис метода:

[атрибуты] [спецификторы] тип_возвращаемого_результаты имя_метода ([список_параметров])

{

тело_метода;

return значение

}

где:

1) Атрибуты и спецификторы являются необязательными элементами синтаксиса описания метода. На данном этапе атрибуты нами использоваться не будут, а из всех спецификаторов мы в обязательном порядке будем использовать спецификатор static, который позволит обращатся к методу класса без создания его экземпляра.

Замечание. Остальные спецификаторы мы рассмотрим в разделе «классы».

2) Тип_возвращаемого_результата определяет тип значения, возвращаемого методом. Это может быть любой тип, включая типы классов, создаваемые программистом. Если метод не возвращает никакого значения, необходимо указать тип void (в этом случае в теле метода отсутсвует оператор return).

3) Имя_метода – идентификатор, заданный программистом с учетом требований накладываемыми на идентификаторы в С#, отличный от тех, которые уже использованы для других элементов программы в пределах текущей области видимости.

4) Список_параметров представляет собой последовательность пар, состоящих из типа данных и идентификатора, разделенных запятыми. Параметры — это переменные или константы, которые получают значения, передаваемые методу при вызове. Если метод не имеет параметров, то список_параметров остается пустым.

5) Значение определяет значение, возвращаемое методом. Тип значения должен соответствовать типу_возвращаемого_результата или приводится к нему.

Рассмотрим простейший пример метода:

class Program

{

static void Func() //дополнительный метод

{

Console.Write("x= ");

double x=double.Parse(Console.ReadLine());

double y = 1 / x;

Console.WriteLine("y({0})={1}", x,y );

}

static void Main() //точка входа в программу

{

Func(); //первый вызов метода Func

Func(); //второй вызов метода Func

}

}

В даном примере в метод Func не передаются никакие значения, поэтому список параметров пуст. Кроме того метод ничего не возвращает, поэтому тип возвращаемого значения void. В основном методе Main мы вызвали метод Func два раза. Если будет необходимо, то данный метод можно будет вызвать еще столько раз, сколько потребуется для решения задачи.

Задания.

1. Добавьте в метод Main третий вызов метода Func.

2. Преобразуйте программу так, чтобы метод Func вызывался n раз.

Изменим исходный пример так, чтобы в него передавалось значение х, а сам метод возвращал значение y.

class Program

{

static double Func( double x) //дополнительный метод

{

return 1 / x; //Возвращаемое значение

}

static void Main() //точка входа в программу

{

Console.Write("a=");

double a=double.Parse(Console.ReadLine());

Сonsole.Write("b=");

double b=double.Parse(Console.ReadLine());

for (double x = a; x <= b; x += 0.5)

{

double y = Func(x); //вызов метода Func

Console.WriteLine("y({0:f1})={1:f2}", x, y);

}

}

В данном примере метод Func содержит параметр х, тип которого double. Для того, чтобы метод Func возвращал в вызывающий его метод Main значение выражения 1/x (тип которого double), перед именем метода указывается тип возвращаемого значения – double, а в теле метода используется оператор передачи управления – return. Оператор return завершает выполнение метода и передает управление в точку его вызова.

Задания. Преобразуйте программу так, чтобы метод Func возвращал значение выражения:

1. x²; 2.

Рассмотрим другой пример:

class Program

{

static int Func( int x, int y) //сторка 1

{

return (x>y)? x:y;

}

static void Main()

{

Console.Write("a=");

int a = int.Parse(Console.ReadLine());

Console.Write("b=");

int b = int.Parse(Console.ReadLine());

Console.Write("c=");

int c = int.Parse(Console.ReadLine());

int max = Func(Func(a, b), c); //строка 2 - вызовы метода Func

Console.WriteLine("max({0}, {1}, {2})={3}", a, b, c, max);

}

}

В данном примере метод Func имеет два целочисленных параметра – x, y, а в качестве результата метод возвращает наибольшее из них. На этапе описания метода (строка 1) указываются формальных параметры, на этапе вызова (строка 2) в метод передаются фактические параметры, которые по количеству и по типу совпадают с формальными параметрами. Если количество фактических и формальных параметров будет различным, то компилятор выдаст соответствующее сообщение об ошибке. Если параметры будут отличаться типами, то компилятор попытается выполнить неявное преобразование типов. Если неявное преобразование невозможно, то также будет сгенерирована ошибка.

Обратите внимание на то, что при вызове метода Func использовалось вложение одного вызова в другой.

Задание. Преобразуйте программу так, чтобы с помощью метода Func можно было найти наибольшее значение из четырех чисел: a, b, c, d. Метод Func при этом не изменять.

В общем случае параметры используются для обмена информацией между вызывающим и вызываемым методами. В С# для обмена предусмотрено четыре типа параметров: параметры-значения, параметры-ссылки, выходные параметры, параметры-массивы.

При передаче параметра по значению метод получает копии параметров, и операторы метода работают с этими копиями. Доступа к исходным значениям параметров у метода нет, а, следовательно, нет и возможности их изменить.

Замечание. Все примеры, рассмотренные ранее, использовали передачу данных по значению.

Рассмотрим небольшой пример:

class Program

{

static void Func(int x)

{

x += 10; // изменили значение параметра

Console.WriteLine("In Func: " + x);

}

static void Main()

{

int a=10;

Console.WriteLine("In Main: "+ a);

Func(a);

Console.WriteLine("In Main: " + a);

}

}

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

In Main: 10

In Func: 20

In Main: 10

В данном примере значение формального параметра х было изменено в методе Func, но эти изменения не отразились на фактическом параметре а метода Main.

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

class Program

{

static void Func(int x, ref int y)

{

x += 10; y += 10; //изменение параметров

Console.WriteLine("In Func: {0}, {1}", x, y);

}

static void Main()

{

int a=10, b=10; // строка 1

Console.WriteLine("In Main: {0}, {1}", a, b);

Func(a, ref b);

Console.WriteLine("In Main: {0}, {1}", a, b);

}

}

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

In Main: 10 10

In Func: 20 20

In Main: 10 20

В данном примере в методе Func были изменены значения формальных параметров х и y. Эти изменения не отразились на фактическом параметре а, т.к. он передавался по значению, но значение b было изменено, т.к. он передавался по ссылке.

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

Однако в некоторых случаях бывает невозможно инициализировать параметр до вызова метода. Тогда параметр следует передавать как выходной, используя спецификатор out.

class Program

{

static void Func(int x, out int y)

{

x += 10; y = 10; // определение значения выходного параметра y

Console.WriteLine("In Func: {0}, {1}", x, y);

}

static void Main()

{

int a=10, b;

Console.WriteLine("In Main: {0}", a);

Func(a, out b);

Console.WriteLine("In Main: {0}, {1}", a, b);

}

}

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

In Main: 10

In Func: 20 10

In Main: 10 10

В данном примере в методе Func формальный параметр y и соответствующий ему фактический параметр b метода Main были помечены спецификатором out. Поэтому значение b до вызова метода Func можно было не определять, но изменение параметра y отразились на изменении значения параметра b.

Замечание. Параметры-массивы будут рассмотрены позже.

Перегрузка методов

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

Рассмотрим следующий пример:

class Program

{

static int max(int a) //первая версия метода max

{

int b = 0;

while (a > 0)

{

if (a % 10 > b) b = a % 10;

a /= 10;

}

return b;

}

static int max(int a, int b) //вторая версия метода max

{

if (a > b) return a;

else return b;

}

static int max(int a, int b, int c) //третья версия метода max

{

if (a > b && a > c) return a;

else if (b > c) return b;

else return c;

}

static void Main()

{

int a = 1283, b = 45, c = 35740;

Console.WriteLine(max(a));

Console.WriteLine(max(a, b));

Console.WriteLine(max(a, b, c));

}

}

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

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

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

Рекурсивным называют метод, если он вызывает сам себя в качестве вспомогательного. В основе рекурсивного метода лежит так называемое «рекурсивное определение» какого-либо понятия. Классическим примером рекурсивного метода является метод, вычисляющий факториал.

Из курса математики известно, что 0!=1!=1, n!=1*2*3…*n. С другой стороны
n!=(n-1)!*n. Таким образом, известны два частных случая параметра n, а именно n=0 и n=1, при которых мы без каких-либо дополнительных вычислений можем определить значение факториала. Во всех остальных случаях, то есть для n>1, значение факториала может быть вычислено через значение факториала для параметра n-1. Таким образом, рекурсивный метод будет иметь вид:

class Program

{

static long F(int n) //рекурсивный метод

{

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

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

else return n*F(n-1); //шаг рекурсии - повторный вызов метода с другим параметром

}

static void Main()

{

Console.Write("n=");

int n =int.Parse( Console.ReadLine());

long f=F(n); //нерекурсивный вызов метода F

Console.WriteLine("{0}!={1}",n, f);

}

}

Рассмотрим работу описанного выше рекурсивного метода для n=3.

1 вызов: n=3

F(3)

{ шаг2 вызов: n=2

return 3*F(2); F(2)

} { шаг3 вызов: n=1

возврат return 2*F(1); F(1)

} ; {

возврат return 1;

}

Первый вызов метода осуществляется из метода Main, в нашем случае командой f=F(3). Этап вхождения в рекурсию обозначим жирными стрелками. Он продолжается до тех пор, пока значение переменной n не становится равной 1. После этого начинается выход из рекурсии (тонкие стрелки). В результате вычислений получается, что F(3)=3*2*1.

Рассмотренный вид рекурсии называют прямой. Метод с прямой рекурсией обычно содержит следующую структуру:

if (<условие>)

<оператор>;

else <вызов данного метода с другими параметрами>;

В качестве <условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивному методу, при которых результат его работы заранее известен, поэтому далее следует простой оператор или блок, а в ветви else происходит рекурсивный вызов данного метода с другими параметрами.

Что необходимо знать для реализации рекурсивного процесса? Со входом в рекурсию осуществляется вызов метода, а для выхода необходимо помнить точку возврата, т.е. то место программы откуда мы пришли и куда нам нужно будет возвратиться после завершения метода. Место хранения точек возврата называется стеком вызовов и для него выделяется определенная область оперативной памяти. В этом стеке запоминаются не только адреса точек возврата, но и копии значений всех параметров. По этим копиям восстанавливается при возврате вызывающий метод. При развертывании рекурсии за счет создания копий параметров возможно переполнение стека. Это является основным недостатком рекурсивного метода. С другой стороны, рекурсивные методы позволяют перейти к более компактной записи алгоритма.

Следует понимать, что любой рекурсивный метод можно преобразовать в обычный метод. И практически любой метод можно преобразовать в рекурсивный, если выявить рекуррентное соотношение между вычисляемыми в методе значениями.

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

Пример 1:Найти сумму цифр числа А.

Известно, что любое натуральное число , где - цифры числа, можно представить следующим образом:

Например, число 1234 можно представить как:

.

Из данного представления видно, что получить последнюю цифру можно, если найти остаток от деления числа на 10. В связи с этим для разложения числа на составляющие его цифры можно использовать следующий алгоритм:

1. Находим остаток при делении числа А на 10, т.е. получаем крайнюю правую цифру числа.

2. Находим целую часть числа при делении A на 10, т.е. отбрасываем от числа A крайнюю правую цифру.

3. Если преобразованное A > 0, то переходим на пункт 1. Иначе число равно нулю и отделять от него больше нечего.

Данный алгоритм будет использоваться при разработке нерекурсивного метода.

С другой стороны, сумму цифр числа 1234 можно представить следующим образом sum(1234)=sum(123)+4=(sum(12)+3)+4=(((sum(1)+2)+3)+4)=(((sum(0)+1)+2)+3)+4. Таким образом, если А=0, то сумма цифр числа также равна нулю, т.е. sum=0. В противном случае сумму цифр числа A можно представить рекуррентным соотношением sum(A)=sum(A/10)+A%10. Полученное рекуррентное соотношение будем использовать при разработке рекурсивного метода.

class Program

{

static long Sum(long a) //нерекусивный метод

{

long sum=0;

while (a>0) //пока a больше нуля

{

sum+=a%10; //добавляем к сумме последнюю цифру числа а

a/=10; //отбрасываем от числа а последнюю цифру

}

return sum; //возвращаем в качестве результата сумму цифр числа a

}

static long SumR(long a) //рекурсивный метод

{

if (a=0) //если a =0, то

return 0; // возвращаем 0

else return SumR(a/10)+ a%10; //иначе обращаемся к рекуррентному соотношению

}

static void Main()

{

Console.Write("n=");

long n=long.Parse(Console.ReadLine());

Console.WriteLine("Нерекурсивный метод: "+Sum(n));

Console.WriteLine("Рекурсивный метод: "+SumR(n));

}

}

}

Задание. Изменить методы так, чтобы на экран выводилось количество цифр в числе n.

Пример 2:вычислить n-ный член последовательности Фиббоначи.

Первые два члена последовательности Фиббоначи равны 1, остальные получаются по рекуррентной формуле a_n=a_n-1+a_n-2.

class Program

{

static int Fb(int n) //нерекурсивный алгоритм

{

int a, a1=1, a2=1;

if (n==1||n==2) return 1;

else

{

for (int i=2; i<=n; ++i)

{

a=a1+a2;

a1=a2;

a2=a;

}

return a1;

}

}

static int FbR(int n) //рекурсивный алгоритм

{

if (n==1 || n==2 )return 1;

else return FbR(n-1)+FbR(n-2);

}

static void Main()

{

Console.Write("n=");

int n=int.Parse(Console.ReadLine());

Console.WriteLine("Нерекурсивный метод: "+Fb(n));

Console.WriteLine("Рекурсивный метод: "+FbR(n));

}

}

Задание. Изменить методы так, чтобы на экран выводилась сумма n элементов последовательности Фиббоначи.

Рассмотренные выше рекурсивные методы возвращали некоторое значение, заданное рекуррентным соотношением. Однако, как мы знаем, не все методы возвращают значение. Кроме того, рассмотренные выше методы определяют простой вариант рекурсивного метода. В общем случае рекурсивный метод включает в себя некоторое множество операторов и один или несколько операторов рекурсивного вызова. Действия могут выполняться после рекурсивного вызова, до рекурсивного вызова, а также и до, и после рекурсивного вызова. Рассмотрим примеры «сложных» рекурсивных методов, не возвращающих значение.

Пример 3. Для заданного значения n вывести на экран n строк, в каждой из которых содержится n звездочек. Например, для n=5 на экран нужно вывести следующую таблицу:

*

**

***

****

*****

class Program

{

static void Stroka(int n) //выводит на экран строку из n звездочек

{

for (int i=1; i<=n; ++i)

{

Console.Write('*');

}

Console.WriteLine();

}

static void Star(int n) //нерекурсивный метод

{

for (int i=1; i<=n;++i) //выводит n строк по i звездочек в каждой

Stroka(i);

}

//рекурсивный метод, где i – номер текущей строки, n – номер последней строк

static void StarR(int i,int n)

{

if (i<=n ) //если номер текущей строки не больше номера последней строки, то

{

Stroka(i); //выводим i звездочек в текущей строке и

StarR(i+1,n); //переходим к формированию следующей строки

}

}

static void Main()

{

Console.Write("n=");

int n=int.Parse(Console.ReadLine());

Console.WriteLine("Нерекурсивный метод: ");

Star(n);

Console.WriteLine("Рекурсивный метод: ");

StarR(1,n); // параметр 1 – это номер первой строки, n – номер последней строки

}

}

Задание. Изменить методы так, чтобы для заданного значения n (в нашем случае для n=5) на экран выводилась следующая таблица:

*****

****

***

**

*

Пример 4. Для заданного значения n (например для n=7) вывести на экран следующую таблицу:

*******

*****

***

*

*

***

*****

*******

Данную таблицу условно можно разделить на две части. Рассмотрим отдельно верхнюю часть:

Номер строки	Содержимое экрана	i - количество пробелов в строке	Количество звездочек в строке
	******* ***** *** *

Таким образом, если нумеровать строки с нуля, то номер строки совпадает с количеством пробелов, которых нужно напечатать в начале этой строки. При этом количество звездочек в строке, можно определить по формуле n-2i, где n – это количество звездочек в нулевой строке. Так как количество звездочек в каждой строке уменьшается на 2, то всего нужно напечатать n/2+1 строк.

Аналогичную зависимость можно выявить и для нижней части таблицы.

class Program

{

static void Stroka(int n, char a) //выводит на экран n раз символ а

{

for (int i=1; i<=n; ++i)

{

Console.Write(a);

}

}

static void Star(int n) //нерекурсивный метод

{

for (int i=0; i<=n/2;++i) //выводим верхнюю часть таблицы, в которой в каждой строке вначале

{

Stroka(i,' '); //печатаем пробелы

Stroka(n-2*i,'*'); //затем звездочки

Console.WriteLine(); //затем переводим курсор на новую строку

}

for (int i=n/2; i>=0;--i) // аналогично выводим нижнюю часть таблицы

{

Stroka(i,' ');

Stroka(n-2*i,'*');

Console.WriteLine();

}

}

//рекурсивный метод, где i определяет номер текущей строки, n – количество звездочек в строке

static void StarR(int i, int n)

{

if (n>0 )

{

//действия до рекурсивного вызова – позволят вывести верхнюю часть таблицы

Stroka(i, ' ');

Stroka(n, '*');

Console.WriteLine();

//вызываем этот же метод, увеличивая номер строки, и уменьшая количество звездочек в ней

StarR(i+1,n-2);

//действия после рекурсивного вызова – позволят вывести нижнюю часть таблицы

Stroka(i, ' ');

Stroka(n, '*');

Console.WriteLine();

}

}

static void Main()

{

Console.Write("n=");

int n=int.Parse(Console.ReadLine());

Console.WriteLine("Нерекурсивный метод: ");

Star(n);

Console.WriteLine("Рекурсивный метод: ");

StarR(0,n);

}

}

}

Задание. Изменить методы так, чтобы для заданного значения n (в нашем случае для n=7) на экран выводилась следующая таблица:

*

***

*****

*******

*******

*****

***

*

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

Данная программа содержит метод Prim, который возвращает true, если его параметр является простым числом, false – в противном случае. Чтобы установить, является ли число j простым, нужно проверить делимость числа j на все простые числа, не превышающие квадратный корень из j. Перебор таких простых чисел можно организовать так: рассмотреть первое простое число – 2, а затем, используя метод NextPrim, возвращающий следующее за значением ее параметра простое число, получить все простые числа, не превышающие квадрата числа j. В свою очередь метод NextPrim обращается к методу Prim для того, чтобы определить является ли заданное число простым.

Таким образом методы Prim и NextPrim перекрестно вызывают друг друга. В этом и проявляется косвенная рекурсия.

class Program

{

static bool Prim (int j)

{

int k=2; //первое простое число

//значение k «пробегает» последовательность простых чисел, начиная с 2 до корня из j, при

//этом проверяется делится ли j на одно из таких простых чисел

while (k*k<=j && j%k!=0)

k=NextPrim(k); //вызов метода NextPrim

return (j%k==0)?false:true;

}

static int NextPrim(int i)

{

int p=i+1;

while (!Prim(p)) //вызов метода Prim

++p;

return p;

}

static void Main()

{

Console.Write("n=");

int n=int.Parse(Console.ReadLine());

Console.WriteLine("Следующее за {0} простое число равно {1}.", n, NextPrim(n));

}

}

Задание. Изменить программу так, чтобы на экран выводились все простые числа меньшие N.

Рекурсия является удобным средством решения многих задач: сортировки числовых массивов, обхода таких структур данных как деревья и графы.

С другой стороны, применение рекурсивных методов в ряде случаев оказывается нерациональным. Вспомним рекурсивный метод подсчета n-ного члена последовательности Фиббоначи. Данный метод будет работать весьма неэффективно. FbR(17) вычисляется в ней как FbR(16)+ FbR(15). В свою очередь FbR(16) вычисляется в ней как FbR(15)+ FbR(14). Таким образом, FbR(15) будет вычисляться 2 раза, FbR(14) – 3 раза, FbR(13) – 5 раз и т.д. Всего для вычисления FbR(17) потребуется выполнить более тысячи операций сложения. Для сравнения при вычислении Fb(17), т.е. используя не рекурсивный метод, потребуется всего лишь 15 операций сложения.

Таким образом, при разработке рекурсивного метода следует задуматься об его эффективности.

Массив как параметр

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

Рассмотрим пример передачи массива как параметра:

class Program

{

static void Print(int n, int[] a) //n – размерность массива, а – ссылка на массив

{

for (int i = 0; i < n; i++) Console.Write("{0} ", a[i]);

Console.WriteLine();

}

static void Change(int n, int[] a)

{

for (int i = 0; i < n; i++)

if (a[i] > 0) a[i] = 0; // изменяются элементы массива

}

static void Main()

{

int[] myArray = { 0, -1, -2, 3, 4, 5, -6, -7, 8, -9 };

Print(10, myArray);

Change(10, myArray);

Print(10, myArray);

}

}

Задание. Измените программу так, чтобы метод Change удваивал значения положительных элементов массива.