Вопрос № 15. Рекурсивная функция, примеры

Рекурсивной называется функция, которая вызывает саму себя. Такая рекурсия называется прямой. Существует еще косвенная рекурсия, когда две или более функций вызывают друг друга.

В обязательном порядке для завершения вычислений рекурсивная функция должна содержать хотя бы одну не рекурсивную ветвь, заканчивающуюся оператором возврата.

Каждый рекурсивный вызов порождает новый набор формальных параметров и локальных переменных, старый набор не уничтожается, а сохраняется в стеке по принципу вложенности:

1) в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров;

2) при вызове функции в стек записывается точка возврата (этой адрес той части программы, где находится вызов функции).

3) в начале тела функции в стеке резервируется место для локальных переменных.

В стеке будет содержаться история рекурсивных вызовов в виде цепочки фрагментов. А программа в каждый момент времени работает с последним вызовом.

При завершении рекурсии программа возвращается к предыдущей версии рекурсивной функции, соответственно работает с предыдущим фрагментом в стеке.

Для написания рекурсии в стеке надо уметь выделять шаг процесса. При этом начальные условия шага это формальные параметры функции, а начальные условия следующего шага, это фактические параметры рекурсивного вызова.

Вопрос №16. Структуры данных (СД): динамические и статические, с произвольным и с последовательным доступом. Абстрактный тип данных. Характерные особенности АТД (обобщение и инкапсуляция)

Тип данных - это «шаблон» по которому выделяется память при объявлении переменных.

Типы данных бывают базовыми и производными.

Абстрактный тип данных(АТД) – это совокупность физически и логически (определяется неким алгоритмом) взаимосвязанных переменных и их значений.

Другое определение АТД – это математическая модель + различные операторы, определенные в рамках этой модели.

К АТД относятся:

l последовательность;

l стек;

l очередь;

l дек;

l однонаправленный линейный список;

l двунаправленный линейный список.

Реализация АТД возможна, используя: 1) непрерывную область памяти, как правило реализует стек, 2) динамическая реализация.