 |
19. Рекурсивные методы. Прямая рекурсия.
|
|
|
|
19. Рекурсивные методы. Прямая рекурсия.
Рекурсивным называют метод, если он вызывает сам себя в качестве вспомогательного. В основе рекурсивного метода лежит так называемое " рекурсивное определение" какого-либо понятия. Классическим примером рекурсивного метода является метод, вычисляющий факториал.
Рассмотренный вид рекурсии называют прямой. Метод с прямой рекурсией обычно содержит следующую структуру:
if (< условие> )
< оператор>;
else < вызов данного метода с другими параметрами>;
В качестве < условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивному методу, при которых результат его работы заранее известен, поэтому далее следует простой оператор или блок, а в ветви else происходит рекурсивный вызов данного метода с другими параметрами.
Со входом в рекурсию осуществляется вызов метода, а для выхода необходимо помнить точку возврата, т. е. то место программы откуда мы пришли и куда нам нужно будет возвратиться после завершения метода. Место хранения точек возврата называется стеком вызовов и для него выделяется определенная область оперативной памяти. При развертывании рекурсии за счет создания копий параметров возможно переполнение стека. Это является основным недостатком рекурсивного метода. С другой стороны, рекурсивные методы позволяют перейти к более компактной записи алгоритма.
Следует понимать, что любой рекурсивный метод можно преобразовать в обычный метод. И практически любой метод можно преобразовать в рекурсивный, если выявить рекуррентное соотношение между вычисляемыми в методе значениями.
Пример 1: Найти сумму цифр числа А.
|
|
|
class Program
{ static long Sum(long a) //нерекусивный метод {
long sum=0;
while (a> 0) //пока a больше нуля
{ sum+=a%10; //добавляем к сумме последнюю цифру числа а
a/=10; //отбрасываем от числа а последнюю цифру }
return sum; //возвращаем в качестве результата сумму цифр числа a }
static long SumR(long a) //рекурсивный метод
{ if (a==0) //если a =0, то
return 0; // возвращаем 0
else return SumR(a/10)+ a%10; //иначе обращаемся к рекуррентному соотношению }
static void Main()
{ Console. Write(" n=" );
long n=long. Parse(Console. ReadLine());
Console. WriteLine(" Нерекурсивный метод: " +Sum(n));
Console. WriteLine(" Рекурсивный метод: " +SumR(n)); } }}
20. Рекурсивные методы. Косвенная рекурсия.
Однако существует еще и косвенная рекурсия, в которой метод вызывает себя в качестве вспомогательного не непосредственно, а через другой вспомогательный метод. Косвенную рекурсию демонстрирует следующая программа, которая для заданного значения n выводит на экран следующее за ним простое число.
Данная программа содержит метод Prim, который возвращает true, если его параметр является простым числом, false – в противном случае. Чтобы установить, является ли число j простым, нужно проверить делимость числа j на все простые числа, не превышающие квадратный корень из j. Перебор таких простых чисел можно организовать так: рассмотреть первое простое число – 2, а затем, используя метод NextPrim, возвращающий следующее за значением ее параметра простое число, получить все простые числа, не превышающие квадрата числа j. В свою очередь метод NextPrim обращается к методу Prim для того, чтобы определить является ли заданное число простым.
Таким образом методы Prim и NextPrim перекрестно вызывают друг друга. В этом и проявляется косвенная рекурсия.
class Program
{
static bool Prim (int j)
{
int k=2; //первое простое число
//значение k " пробегает" последовательность простых чисел, начиная с 2 до корня из j, при
//этом проверяется делится ли j на одно из таких простых чисел
|
|
|
while (k*k< =j & & j%k! =0)
k=NextPrim(k); //вызов метода NextPrim
return (j%k==0)? false: true;
}
static int NextPrim(int i)
{
int p=i+1;
while (! Prim(p)) //вызов метода Prim
++p;
return p;
}
static void Main()
{
Console. Write(" n=" );
int n=int. Parse(Console. ReadLine());
Console. WriteLine(" Следующее за {0} простое число равно {1}. ", n, NextPrim(n));
}
}
Рекурсия является удобным средством решения многих задач: сортировки числовых массивов, обхода таких структур данных как деревья и графы.
С другой стороны, применение рекурсивных методов в ряде случаев оказывается нерациональным.
38. Обработка событий клавиатуры.
Большинство программ Windows Forms обрабатывают ввод данных с клавиатуры с помощью обработки событий клавиатуры.
Windows Forms содержит два события, возникающие при нажатии клавиши на клавиатуре, и одно событие, возникающее, когда пользователь отпускает клавишу:
Событие KeyDown, которое происходит один раз.
Событие KeyPress, которое может возникать несколько раз, когда пользователь удерживает нажатую клавишу.
Событие KeyUp, которое возникает один раз после того, как пользователь отпускает клавишу.
Когда пользователь нажимает клавишу, Windows Forms определяет, какое событие вызвать на основании того, на какую клавишу указывает сообщение клавиатуры — клавишу со знаком или физическую клавишу.
KeyDown - Это событие возникает при нажатии физической клавиши пользователем.
Обработчик события KeyDown получает следующие параметры.
Параметр KeyEventArgs, который предоставляет свойство KeyCode (которое указывает на физическую клавишу клавиатуры).
Свойство Modifiers (клавиши SHIFT, CTRL или ALT).
Свойство KeyData (которое объединяет код клавиши и клавишу CTRL, SHIFT или ALT).
KeyPress - Это событие возникает при нажатии клавиши или клавиш, которое привело к вводу знака. Например, пользователь нажимает клавишу SHIFT и клавишу буквы " a" нижнего регистра, что приводит к вводу знака прописной буквы " A".
Событие KeyPress возникает после события KeyDown.
Обработчик события KeyPress получает следующие параметры.
Параметр KeyPressEventArgs, который содержит код знака нажатой клавиши. Этот код уникален для каждой комбинации клавиш символов и клавиш CTRL, SHIFT или ALT.
KeyUp - Это событие возникает при отпускании физической клавиши пользователем.
Обработчик события KeyUp получает следующие параметры.
Параметр KeyEventArgs, который предоставляет свойство KeyCode (указывающее физическую клавишу клавиатуры);
свойство Modifiers (клавиши SHIFT, CTRL или ALT);
свойство KeyData (которое объединяет код клавиши и клавишу CTRL, SHIFT или ALT).
|
|
|
