Полное руководство. С# 4.0

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; } } Вот к какому результату приводит выполнение этого кода.