Главная arrow Язык программирования C# arrow C# Полное руководство Герберт Шилдт arrow Рекурсия C# Полное руководство Герберт Шилдт

Рекурсия C# Полное руководство Герберт Шилдт

В языке C# допускается, чтобы метод вызывал самого себя. Этот процесс называется рекурсией, а метод, вызывающий самого себя, — рекурсивным. Вообще, рекурсия представляет собой процесс, в ходе которого нечто определяет самое себя. В этом отношении она чем-то напоминает циклическое определение. Рекурсивный метод отличается главным образом тем, что он содержит оператор, в котором этот метод вызывает самого себя. Рекурсия является эффективным механизмом управления программой.
Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1x2x3, или 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) *п. Для вычисления этого произведения метод FactR () вызывается с аргументом n-1. Этот процесс повторяется до тех пор, пока значение аргумента п не станет равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, когда вычисляется факториал числа 2, то при первом вызове метода FactR () происходит второй его вызов с аргументом 1. Из этого вызова возвращается значение 1, которое затем умножается на 2 (первоначальное значение аргумента п). В итоге возвращается результат 2, равный факториалу числа 2 (1x2). Было бы любопытно ввести в метод FactR () операторы, содержащие вызовы метода WriteLine(), чтобы наглядно показать уровень рекурсии при каждом вызове метода FactR(), а также вывести промежуточные результаты вычисления факториала заданного числа.
Когда метод вызывает самого себя, в системном стеке распределяется память для новых локальных переменных и параметров, и код метода выполняется с этими новыми переменными и параметрами с самого начала. При рекурсивном вызове метода не создается его новая копия, но лишь используются его новые аргументы. А при возврате из каждого рекурсивного вызова старые локальные переменные и параметры извлекаются из стека и выполнение возобновляет с точки вызова в методе. Рекурсивные методы можно сравнить по принципу действия с постепенно сжимающейся и затем распрямляющейся пружиной.
Ниже приведен еще один пример рекурсии для вывода символьной строки в обратном порядке. Эта строка задается в качестве аргумента рекурсивного метода DisplayRev ().

// Вывести символьную строку в обратном порядке,
// используя рекурсию.

using System;

class RevStr {

   // Вывести символьную строку в обратном порядке.
   public void DisplayRev(string str) {
      if(str.Length > 0)
         DisplayRev(str.Substriпg (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 (). При возврате из каждого такого вызова выводится первый символ строки, представленной аргументом str, а в итоге вся строка выводится в обратном порядке.
Рекурсивные варианты многих процедур могут выполняться немного медленнее, чем их итерационные эквиваленты из-за дополнительных затрат системных ресурсов на неоднократные вызовы метода. Если же таких вызовов окажется слишком много, то в конечном итоге может быть переполнен системный стек. А поскольку параметры и локальные переменные рекурсивного метода хранятся в системном стеке и при каждом новом вызове этого метода создается их новая копия, то в какой-то момент стек может оказаться исчерпанным. В этом случае возникает исключительная ситуация и общеязыковая исполняющая среда (CLR) генерирует соответствующее исключение. Но беспокоиться об этом придется лишь в том случае, если рекурсивная процедура выполняется неправильно.
Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения.
При написании рекурсивных методов следует непременно указать в соответствующем месте условный оператор, например if, чтобы организовать возврат из метода без рекурсии. В противном случае возврата из вызванного однажды рекурсивного метода может вообще не произойти. Подобного рода ошибка весьма характерна для реализации рекурсии в практике программирования. В этом случае рекомендуется пользоваться операторами, содержащими вызовы метода WriteLine(), чтобы следить за происходящим в рекурсивном методе и прервать его выполнение, если в нем обнаружится ошибка.