|
Читайте также: |
Подпрограмма называется рекурсивной, если она вызывает саму себя (прямая рекурсия) или вызывает другую подпрограмму, которая, в свою очередь, обращается к первой (косвенная рекурсия).
В случае прямой рекурсии вызов функцией самой себя делается непосредственно в этой же функции. Косвенная рекурсия создаётся за счёт вызова данной функции из какой-либо другой функции, которая сама вызывалась из данной функции.
Не зависимо от того, какой вид рекурсии используется (прямая или косвенная), в рекурсивной функции обязательно должна выполняться проверка какого-либо условия, в зависимости от которого осуществлялся бы выход из рекурсивной функции. Причём, необходимо гарантировать, что это условие обязательно будет выполнено через конечное количество рекурсивных вызовов, и функция в конце концов закончит работу. Иначе — аварийное завершение. Последовательный вызов функцией самой себя называют рекурсивным спуском, последовательный выход из многократного вызова — рекурсивным подъёмом.
Классическими рекурсивными алгоритмами могут быть возведение числа в целую положительную степень, вычисление факториала.
При написании рекурсивных функций следует иметь оператор if, чтобы заставить функцию вернуться без рекурсивного вызова. Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно. Это наиболее типичная ошибка, связанная с написанием рекурсивных функций. Надо использовать при разработке функции printf() и getchar(), чтобы можно было узнать, что происходит, и прекратить выполнение в случае обнаружения ошибки.
Рекурсия позволяет в ряде случаев создавать очень компактный код, особенно в том случае, когда при постановке задачи определение каких-либо понятий имеет явно рекурсивный вид.
13. Динамические структуры данных. Однонаправленный список
Не редко в структурах используют списки, потому что с ними удобнее работать, чем с массивами, когда не знаешь точное количество данных, когда в процессе работы приходится добавлять и удалять элементы.
Линейный список — это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (next). Поле ссылки последнего элемента должно содержать пустой указатель (NULL).
struct Data
{
int a;
};
struct List
{
Data d;
List *next;
};
Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.
Дата добавления: 2014-11-24; просмотров: 111 | Поможем написать вашу работу | Нарушение авторских прав |