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

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

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

long F(int n)

{

// Дошли до 0 или 1?

if (n == 0 || n == 1)

// Нерекурсивная ветвь

return 1;

else

// Шаг рекурсии: повторный вызов

// метода с другим параметром

return n * F(n - 1);

}

// Пример вызова рекурсивного метода

long f = F(3);

MessageBox.Show(f.ToString());

Рассмотрим работу описанного выше рекурсивного метода для n=3.

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

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

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

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

<оператор>;

Else

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

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

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

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

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

Рис. 15.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 и y на 50

x += 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, значение которой определяет текущую вложенность рекурсии (сколько вызовов рекурсии еще будет).

Дата добавления: 2014-11-07