2014-02-24
642
Лекция 3
Сложная рекурсия
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.
Пример:
| procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры} procedure B(n: integer); {Опережающее описание второй процедуры} procedure A(n: integer); {Полное описание процедуры A} begin writeln(n); B(n-1); end; procedure B(n: integer); {Полное описание процедуры B} begin writeln(n); if n<10 then A(n+2); end; |
Опережающее описание процедуры B позволяет вызывать ее из процедуры A. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.
Если обычную рекурсию можно уподобить змее, пожирающий свой хвост, то образ сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию.
|
|
|
Структуры данных служат базовыми элементами любой машинной программы. В организации структур данных и процедур их обработки заложена возможность проверки правильности работы программы.
Никлас Вирт.
Без понимания структур данных и алгоритмов невозможно создать сколько-нибудь серьезный программный продукт. И слова эпиграфа служат тому подтверждением. Поэтому главная задача данной лекции заключается в следующем:
ü показать все разнообразие имеющихся структур данных, представление их в памяти на физическом уровне, т.е. "как это сделано внутри", и логическом уровне, или как эти структуры реализованы в языках программирования;
ü выполняемые над ними операции физического и логического уровней;
ü показать значение структурного подхода к разработке алгоритмов, продемонстрировать порядок разработки алгоритмов наиболее, по мнению авторов, интересных задач.
Нельзя сказать, что такие вопросы не рассматривались в литературе, но с полной уверенностью можно отметить, что так сконцентрировано, так подробно и в доступной для понимания форме, с таким количеством демонстрационных примеров ни в каком из известных изданиях не сделано.
В лекции приводится классификация структур данных, обширная информация о физическом и логическом представлении структур данных всех классов памяти ПВМ: простых, статических, полустатических, динамических; исчерпывающая информация об операциях над всеми перечисленными структурами. Рассмотрим большое количество алгоритмов особенно важных операций, реализованных в виде процедур и функций, написанных на Turbo Pascal, которые могут быть применены как "заготовки" в самостоятельных разработках студентов и программистов.
