Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Лабораторная работа 14. Рекурсивные Методы
Цель лабораторной работы: изучить рекурсивные методы, написать программу с использованием рекурсии. Общие понятия Рекурсивным называют метод, если он вызывает сам себя в качестве вспомогательного. В основе рекурсивного метода лежит так называемое "рекурсивное определение" какого-либо понятия. Классическим примером рекурсивного метода является метод, вычисляющий факториал. Из курса математики известно, что 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, значение которой определяет текущую вложенность рекурсии (сколько вызывов рекурсии еще будет).
|
|||||
Последнее изменение этой страницы: 2017-02-07; просмотров: 831; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.202.128.177 (0.065 с.) |