Лабораторный практикум по информатике
жүктеу/скачать 1,1 Mb.
|
- Бұл бет үшін навигация:
- Общие понятия
ЛАБОРАТОРНАЯ РАБОТА № 14.РЕКУРСИЯ Цель лабораторной работы: изучить рекурсивные методы, напи- сать программу с использованием рекурсии. Общие понятияРекурсивным называют метод, если он вызывает сам себя в качестве вспомогательного. В основе рекурсивного метода лежит так называемое рекурсивное определение какого-либо понятия. Классическим примером рекурсивного метода является метод, вычисляющий факториал. Из курса математики известно, что 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); }
Рассмотрим работу описанного выше рекурсивного метода для n = 3. Первый вызов метода осуществляется из основной программы, в нашем случае командой f = F(3). Этап вхождения в рекурсию обо- значим стрелками с подписью «шаг». Он продолжается до тех пор, пока значение переменной n не становится равным 1. После этого начинается выход из рекурсии (стрелки с подписью «возврат»). В результате вы- числений получается, что F(3) = 3 * 2 * 1. Рис. 14.1. Структура рекурсивных вызовов Рассмотренный вид рекурсии называют прямой. Метод с прямой рекурсией обычно содержит следующую структуру: if (<условие>)
else
<вызов этого же метода с другими параметрами>; В качестве <условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивному методу, при которых результат его работы заранее известен, поэтому далее следует простой оператор или блок, а в ветви else происходит рекурсивный вызов дан- ного метода с другими параметрами. Что необходимо знать для реализации рекурсивного процесса? Со входом в рекурсию осуществляется вызов метода, а для выхода не- обходимо помнить точку возврата, т. е. то место программы, откуда мы пришли и куда нам нужно будет возвратиться после завершения метода. Место хранения точек возврата называется стеком вызовов, и для него выделяется определенная область оперативной памяти. В этом стеке за- поминаются не только адреса точек возврата, но и копии значений всех параметров. По этим копиям восстанавливается при возврате вызываю- щий метод. При развертывании рекурсии за счет создания копий пара- метров возможно переполнение стека. Это является основным недос- татком рекурсивного метода. С другой стороны, рекурсивные методы позволяют перейти к более компактной записи алгоритма. Следует понимать, что любой рекурсивный метод можно преобра- зовать в обычный метод с использованием циклов. И практически лю- бой метод можно преобразовать в рекурсивный, если выявить рекур- рентное соотношение между вычисляемыми в методе значениями. Рассмотрим пример кода для создания набора самоподобных структур. В нашем случае это будет набор увеличивающихся квадра- тов (рис. 14.2). Рис. 14.2. Набор квадратов При проектировании данной программы были созданы два метода: private void MyDraw(Graphics g, int N, int x, int y) { if (N == 0) return; else { } // Отрисовка прямоугольника rawRectangle(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, значение которой определяет текущую вложенность ре- курсии (сколько вызовов рекурсии еще будет). жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|