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

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

Из курса математики известно, что 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 происходит рекурсивный вызов данного метода с другими параметрами.

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

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

I. Разработать рекурсивный метод (возвращающий значение). Сравните результаты с нерекурсивным методом:

Пример 1: вычислить 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) //рекурсивный алгоритм

{ Нерекурсивный метод: "+Fb(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));

}

}

1. для вычисления n-го члена следующей последовательности .

2. для вычисления n-го члена следующей последовательности .

3. для нахождения наибольшего общего делителя методом Евклида:

4. для вычисления значения функции Аккермана для неотрицательных чисел n и m. Функция Аккермана определяется следующим образом:

5. для вычисления числа сочетаний C(n, m) где , используя следующие свойства

при 0<m<n.

6. вычисляющий число а, для которого выполняется неравенство , где n – натуральное число. Для подсчета числа а использовать формулу:

7. для вычисления (x –вещественное, , а n –целое) по формуле:

. Вычислить значение для различных x и n.

8. для вычисления , где n – натуральное число. Для заданных натуральных чисел m и k вычислить с помощью разработанного метода значение выражения .

9. для вычисления значения функции .

Найти ее значение при заданном натуральном N.

10. для вычисления цепной дроби: . Найти значение данной дроби при заданном натуральном n.

II. Разработка рекурсивных методов (не возвращающих значений):

Пример 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);

}

}

}

1. Даны первый член и разность арифметической прогрессии. Написать рекурсивный метод для нахождения n-го члена и суммы n первых членов прогрессии.

2. Даны первый член и знаменатель геометрической прогрессии. Написать рекурсивный метод для нахождения n-го члена и суммы n первых членов прогрессии.

3. Разработать рекурсивный метод, который по заданному натуральному числу N (N³1000) выведет на экран все натуральные числа не больше N в порядке возрастания. Например, для N=8, на экран выводится 1 2 3 4 5 6 7 8.

4. Разработать рекурсивный метод, который по заданному натуральному числу N (N³1000) выведет на экран все натуральные числа не больше N в порядке убывания. Например, для N=8, на экран выводится 8 7 6 5 4 3 2 1.

5. Разработать рекурсивный метод для вывода на экран стихотворения:

10 лунатиков жили на луне

10 лунатиков ворочались во сне

Один из лунатиков упал с луны во сне

9 лунатиков осталось на луне

9 лунатиков жили на луне

9 лунатиков ворочались во сне

Один из лунатиков упал с луны во сне

8 лунатиков осталось на луне

…...

И больше лунатиков не стало на луне

6. Дано натуральное число n. Разработать рекурсивный метод для вывода на экран следующей последовательности чисел:

…
n	n	n	…	n

7. Дано натуральное число n. Разработать рекурсивный метод для вывода на экран следующей последовательности чисел:

…
n	n-1	n-2	…

8. Разработать рекурсивный метод для вывода на экран цифр натурального числа в прямом порядке. Применить эту процедуру ко всем числам из интервала от А до В.

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

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

11. Разработать рекурсивный метод для вывода на экран всех делителей заданного натурального числа n.

12. Дано натуральное четное число n. Разработать рекурсивный метод для вывода на экран следующей картинки:

*********	(0 пробелов, n звездочек)
********	(1 пробел, n-1 звездочка)
*******	(2 пробела, n-2 звездочки)
…
*	(n-1 пробел, 1 звездочка)

13. Дано натуральное четное число n. Разработать рекурсивный метод для вывода на экран следующей картинки:

* *	(n пробелов между звездочками)
** **	(n-2 пробела)
*** ***	(n-4 пробела)
…	…
***** *****	(2 пробела)
**********	(0 пробелов)
***** *****	(2 пробела)
…	…
*** ***	(n-4 пробела)
** **	(n-2 пробела)
* *	(n пробелов

14. Дано натуральное число n. Разработать рекурсивный метод для вывода на экран следующей картинки:

	(1 раз)
	(3 раза)
	(5 раз)
…	(n раз)
	(5 раз)
	(3 раза)
	(1 раз)

15. Разработать рекурсивный метод для вывода на экран следующей картинки: