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

Пример 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 – номер последней строки
    }  
  }

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

* * * * * * *
  * * * * *
    * * *
      *
      *
    * * *
  * * * * *
* * * * * * *

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

Таким образом, если нумеровать строки с нуля, то номер строки совпадает с количеством пробелов, которых нужно напечатать в начале этой строки. При этом количество звездочек в строке, можно определить по формуле 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 выводит на экран следующее за ним простое число.

Данная программа содержит метод 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 -ного члена последовательности Фиббоначи. Данный метод будет работать весьма неэффективно. 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 операций сложения.

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

Практикум

10 лунатиков жили на луне
10 лунатиков ворочались во сне
Один из лунатиков упал с луны во сне
9 лунатиков осталось на луне
9 лунатиков жили на луне
9 лунатиков ворочались во сне
Один из лунатиков упал с луны во сне
8 лунатиков осталось на луне
......
И больше лунатиков не стало на луне

Самостоятельная работа

Задача 1. Разработать рекурсивный метод для вывода на экран всех возможных разложений натурального числа n на множители (без повторений). Например, для n=12 на экран должно быть выведено:

2*2*3=12
2*6=12
3*4=12

Задача 2. Разработать рекурсивный метод для вывода на экран всех возможных разложений натурального числа n на слагаемые (без повторений). Например, для n=5 на экран должно быть выведено:

1+1+1+1+1=5
1+1+1+2=5
1+1+3=5
1+4=5
2+1+2=5
2+3=5