Лабораторная работа 14. Рекурсивные Методы

↑

▷ Содержание

⇐ ПредыдущаяСтр 20 из 23Следующая ⇒

▷ Похожие статьи

Цель лабораторной работы: изучить рекурсивные методы, написать программу с использованием рекурсии.

Общие понятия

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

Из курса математики известно, что 0!=1!=1, n!=1*2*3…*n. С другой стороны n!=(n -1)!* n. Таким образом, известны два частных случая параметра n, а именно n = 0 и n =1, при которых мы без каких-либо дополнительных вычислений можем определить значение факториала. Во всех остальных случаях, то есть для n >1, значение факториала может быть вычислено через значение факториала для параметра n -1. Таким образом, рекурсивный метод будет иметь вид:

{

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.

Рис. 14.1. Структура рекурсивных вызывов

Первый вызов метода осуществляется из метода Main, в нашем случае командой f=F(3). Этап вхождения в рекурсию обозначим жирными стрелками. Он продолжается до тех пор, пока значение переменной n не становится равной 1. После этого начинается выход из рекурсии (тонкие стрелки). В результате вычислений получается, что F(3)=3*2*1.

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

if (<условие>)

<оператор>;

else <вызов данного метода с другими параметрами>;

В качестве <условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивному методу, при которых результат его работы заранее известен, поэтому далее следует простой оператор или блок, а в ветви else происходит рекурсивный вызов данного метода с другими параметрами.

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

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

Рассмотрим пример кода для создания набора самоподобных стуктур. В нашем случае это будет набор увеличивающихся квадратов (рис. 14.2.).

Рис. 14.2. Набор квадратов

При проектировании данной программы были созданы два метода:

private void MyDraw(Graphics g, int N, int x, int y)

{

if (N == 0) return;

else

{ //отрисовка прямоугольника

g.DrawRectangle(new Pen(Brushes.Blue, 2), 0, 0, x, y);

x += 50; //увеличение x на 50

y += 50; //увеличение y на 50

N--;

MyDraw(g, N, x, y); //рекурсивный вызов с новыми параметрами

}

}

private void Form1_Paint(object sender, PaintEventArgs e)

{

Graphics g = e.Graphics;

MyDraw(g, 7, 50, 50); //первый вызов метода и вход в рекурсию

}

Координаты левого верхнего угла всех прямоугольников не изменны и находятся в точке (0, 0). Поэтому в параметрах метода MyDraw достаточно передавать x и y для правого нижнего угла. Также в параметрах передается N, значение которой определяет текущую вложенность рекурсии (сколько вызывов рекурсии еще будет).

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману