Книга: C# 4.0: полное руководство
Рекурсия
Рекурсия
В C# допускается, чтобы метод вызывал самого себя. Этот процесс называется рекурсией, а метод, вызывающий самого себя, — рекурсивным. Вообще, рекурсия представляет собой процесс, в ходе которого нечто определяет самое себя. В этом отношении она чем-то напоминает циклическое определение. Рекурсивный метод отличается главным образом тем, что он содержит оператор, в котором этот метод вызывает самого себя. Рекурсия является эффективным механизмом управления программой.
Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1х2x3, или 6. В приведенном ниже примере программы демонстрируется рекурсивный способ вычисления факториала числа. Для сравнения в эту программу включен также нерекурсивный вариант вычисления факториала числа.
// Простой пример рекурсии.
using System;
class Factorial {
// Это рекурсивный метод.
public int FactR(int n) {
int result;
if (n == 1) return 1;
result = FactR(n - 1) * n;
return result;
}
// Это итерационный метод.
public int FactI(int n) {
int t, result;
result = 1;
for (t = 1; t <= n; t++) result *= t;
return result;
}
}
class Recursion {
static void Main() {
Factorial f = new Factorial();
Console.WriteLine("Факториалы, рассчитанные рекурсивным методом.");
Console.WriteLine("Факториал числа 3 равен " + f.FactR(3));
Console.WriteLine("Факториал числа 4 равен " + f.FactR(4));
Console.WriteLine("Факториал числа 5 равен " + f.FactR(5));
Console.WriteLine();
Console.WriteLine("Факториалы, рассчитанные итерационным методом.");
Console.WriteLine("Факториал числа 3 равен " + f.FactR(3));
Console.WriteLine("Факториал числа 4 равен " + f.FactR(4));
Console.WriteLine("Факториал числа 5 равен " + f.FactR(5));
}
}
При выполнении этой программы получается следующий результат.
Факториалы, рассчитанные рекурсивным методом.
Факториал числа 3 равен 6
Факториал числа 4 равен 24
Факториал числа 5 равен 120
Факториалы, рассчитанные итерационным методом.
Факториал числа 3 равен 6
Факториал числа 4 равен 24
Факториал числа 5 равен 120
Принцип действия нерекурсивного метода FactI()
вполне очевиден. В нем используется цикл, в котором числа, начиная с 1, последовательно умножаются друг на друга, постепенно образуя произведение, дающее факториал.
А рекурсивный метод FactR()
действует по более сложному принципу. Если метод FactR()
вызывается с аргументом 1, то он возвращает значение 1. В противном случае он возвращает произведение FactR(n-1)*n
. Для вычисления этого произведения метод FactR()
вызывается с аргументом n-1. Этот процесс повторяется до тех пор, пока значение аргумента n не станет равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, когда вычисляется факториал числа 2, то при первом вызове метода FactR()
происходит второй его вызов с аргументом 1. Из этого вызова возвращается значение 1, которое затем умножается на 2 (первоначальное значение аргумента n). В итоге возвращается результат 2, равный факториалу числа 2 (1x2). Было бы любопытно ввести в метод FactR()
операторы, содержащие вызовы метода WriteLine(),
чтобы наглядно показать уровень рекурсии при каждом вызове метода FactR(),
а также вывести промежуточные результаты вычисления факториала заданного числа.
Когда метод вызывает самого себя, в системном стеке распределяется память для новых локальных переменных и параметров, и код метода выполняется с этими новыми переменными и параметрами с самого начала. При рекурсивном вызове метода не создается его новая копия, а лишь используются его новые аргументы. А при возврате из каждого рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и выполнение возобновляется с точки вызова в методе. Рекурсивные методы можно сравнить по принципу действия с постепенно сжимающейся и затем распрямляющейся пружиной.
Ниже приведен еще один пример рекурсии для вывода символьной строки в обратном порядке. Эта строка задается в качестве аргумента рекурсивного метода DisplayRev()
.
// Вывести символьную строку в обратном порядке, используя рекурсию.
using System;
class RevStr {
// Вывести символьную строку в обратном порядке.
public void DisplayRev(string str) {
if (str.Length > 0)
DisplayRev(str.Substring(1, str.Length - 1));
else
return;
Console.Write(str[0]);
}
}
class RevStrDemo {
static void Main() {
string s = "Это тест";
RevStr rsOb = new RevStr();
Console.WriteLine("Исходная строка: " + s);
Console.Write("Перевернутая строка: ");
rsOb.DisplayRev(s);
Console.WriteLine();
}
}
Вот к какому результату приводит выполнение этого кода.
Исходная строка: Это тест
Перевернутая строка: тсет отЭ
Всякий раз, когда вызывается метод DisplayRev(),
в нем происходит проверка длины символьной строки, представленной аргументом str
. Если длина строки не равна нулю, то метод DisplayRev()
вызывается рекурсивно с новой строкой, которая меньше исходной строки на один символ. Этот процесс повторяется до тех пор, пока данному методу не будет передана строка нулевой длины. После этого начнется раскручиваться в обратном порядке механизм всех рекурсивных вызовов метода DisplayRev().
При возврате из каждого такого вызова выводится первый символ строки, представленной аргументом stг
, а в итоге вся строка выводится в обратном порядке.
Рекурсивные варианты многих процедур могут выполняться немного медленнее, чем их итерационные эквиваленты из-за дополнительных затрат системных ресурсов на неоднократные вызовы метода. Если же таких вызовов окажется слишком много, то в конечном итоге может быть переполнен системный стек. А поскольку параметры и локальные переменные рекурсивного метода хранятся в системном стеке и при каждом новом вызове этого метода создается их новая копия, то в какой-то момент стек может оказаться исчерпанным. В этом случае возникает исключительная ситуация, и общеязыковая исполняющая среда (CLR) генерирует соответствующее исключение. Но беспокоиться об этом придется лишь в том случае, если рекурсивная процедура выполняется неправильно.
Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения.
При написании рекурсивных методов следует непременно указать в соответствующем месте условный оператор, например if
, чтобы организовать возврат из метода без рекурсии. В противном случае возврата из вызванного однажды рекурсивного метода может вообще не произойти. Подобного рода ошибка весьма характерна для реализации рекурсии в практике программирования. В этом случае рекомендуется пользоваться операторами, содержащими вызовы метода WriteLine(),
чтобы следить за происходящим в рекурсивном методе и прервать его выполнение, если в нем обнаружится ошибка.
- Управление доступом к членам класса
- Передача объектов методам по ссылке
- Использование модификаторов параметров ref и out
- Использование переменного числа аргументов
- Возврат объектов из методов
- Перегрузка методов
- Перегрузка конструкторов
- Инициализаторы объектов
- Необязательные аргументы
- Именованные аргументы
- Метод Main()
- Рекурсия
- Применение ключевого слова static
- Статические классы