следующие формы рекурсии:
n простая рекурсия;
n параллельная рекурсия;
n взаимная рекурсия.
Рекурсия называется простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Для примера напишем функцию вычисления чисел Фибоначчи (F(1)=1; F(2)=1; F(n)=F(n-1)+F(n-2) при n>2):
(DEFUN FIB (N)
(IF (> N 0)
(IF (OR N=1 N=2) 1
(+ (FIB (- N 1)) (FIB (- N 2))))
‘ОШИБКА_ВВОДА))
Рекурсию называют параллельной, если она встречается одновременно в нескольких аргументах функции:
(DEFUN f...
...(g... (f...) (f...)...)
...)
Рассмотрим использование параллельной рекурсии на примере преобразования списочной структуры в одноуровневый список:
(DEFUN PREOBR (L)
(COND
((NULL L) NIL)
((ATOM L) (CONS (CAR L) NIL))
(T (APPEND
(PREOBR (CAR L))
(PREOBR (CDR L))))))
Рекурсия является взаимной между двумя и более функциями, если они вызывают друг друга:
(DEFUN f...
...(g...)...)
(DEFUN g...
...(f...)...)
Различают два типа указателей в Паскал:
типизированные
нетипизированные.
Типизированные указатели содержат адреса, по которым в памяти размещаются данные определенных типов. Используя эти указатели с данными указанных типов, можно выполнять операции, предусмотренные базовым типом.
Нетипизированные указатели хранят просто адреса, которые не связаны с данными конкретных типов, т.е. они могут хранить адрес переменной любого типа.
При описании типизированного указателя в Паскале необходимо сообщить компилятору, адреса переменных какого типа он может хранить:
var <имя указателя>: ^ <тип адресуемой переменной>;
Описание нетипизированного указателя в Паскале:
var <имя указателя>: ^ pointer;
Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти).
Объявление:
var pC: ^char; // адрес символа
pI: ^integer; // адрес целой переменнойp
R: ^real; // адрес вещ. переменной
s: ^array[1..10] of byte;
p: pointer; // нетипизиров. указатель
Указатели – единственное исключение из общего правила, согласно которому все ресурсы перед использованием должны быть описаны.Для них допускаются описания вида:
Туре рр = ^реrsоn; { тип person еще не определен! }
реrsоn = record { определение типа person }
name: string:
next: рр;
end;
Type
{ правильные объявления типов}
P1=^word; { указатель на данные типа word }
P2=^char; { указатель на данные типа char }
P4=array[1..10] of ^real;
{указатель на массив указателей, ссылающихся на данные типа real }Для указателей, которые не хранят никаких адресов, введена константа «нулевой адрес» с именем nil. Константу nil можно присваивать указателю любого типа.
var m: integer; // целая переменная
pI: ^integer; // указатель
A: array[1..2] of integer; // массив
...
pI:= @ m; // адрес переменной m
pI:= @ A[1]; // адрес элемента массива A[1]
pI:= nil; // нулевой адрес
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
(Stack) (Queue) (DEQ)
Стек — это линейный список с переменной длиной, в котором все операции вставки, удаления и доступа к данным выполняются только на одном из концов списка, называемом вершиной стека.
Применяются и другие названия стека — магазин и очередь, функционирующая по принципу LIFO (Last-In-First-Out - "последним пришел — первым исключается"). Системы программирования для блочно-ориентированных языков (Pascal, С и др.) используют стек для размещения в нем локальных переменных процедур и иных программных блоков. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находится память, содержащая локальные переменные активной в данный момент процедуры.
Очередь — это такой линейный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение — с другой стороны (называемой началом или головой очереди).
Очереди также называют «списками типа FIFO» (First - In - First- Out - «первым пришел — первым исключается»).
В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди.
Дек (от англ. deq - double ended queue, т.е. очередь с двумя концами), представляет собой структуру данных, в которой можно добавлять и удалять элементы с двух сторон.