Рекурсия

...

Begin

Begin

Var

...

Type

Const

End.

Begin

Var

Type

Const

Пример

Массив – упорядоченная совокупность данных одного типа.

Массивы

Var

Type

Const

Const

Var

v1: 22 .. 44;

v2: MyType01;

v3: MyType01 = 6;

MyConst11 = 1; MyConst12 = 7;

MyType02 = MyConst11 .. MyConst12;

MyVar02: MyType02;

Замечание. Тип–Диапазон – порядковый тип.

Все типы переменных, изученные до сих пор – скалярные (простые) типы.

Массив – вектор, матрица,...

Массив – переменная с индексом (со списком индексов).

<Объявление одномерного массива> :: =

<Имя переменной>: array [<Диапазон>] of <Тип элемента>;

<Объявление нескольких многомерных массивов> :: =

<Список имён >: array [<Список диапазонов>] of <Тип элемента>;

или

<Список имён >: <Тип-массив>;

<Тип-массив> :: =

array [<Список диапазонов>] of <Тип элемента >;

<Обращение к элементу массива> :: =

<имя массива> [ <Список значений индексов> ]

MyConst21 = 1; MyConst22 = 8;

MyRange1 = 1 .. 7;

MyRange2 = MyConst21 .. MyConst22;

A: array [1 .. 4] of integer;

A1, A2, A3: array [1 .. 4, -1 .. 7] of double;

A4: array [MyRange1] of double;

A5: array [MyRange1, MyRange2] of double;

A[3]:= 99;

A1[2, 6]:= 5.3;

A2[1][7]:= 4.1e-10;

A3[5, 0]:= 2;

Пример. Заполнить матрицу числами, составляющими треугольник Паскаля.

, . , .

n=16;

MyArrayType = array [0 .. n, 0 .. n] of integer;

procedure PT(var mG: MyArrayType);

// procedure PT(var mG: array [0 .. n, 0 .. n] of integer);

m, k: integer;

for m:= 0 to n do for k:= 0 to n do mG[m, k]:= 0;

mG[0, 0]:= 1;

for m:= 1 to n do

mG[m, 0]:= 1; mG[m, m]:= 1;

for k:= 1 to m-1 do mG[m, k]:= mG[m-1, k] + mG[m-1, k-1];

end;

end;

При решении сложных задач программирования эти задачи разбиваются на более простые подзадачи. Каждая из подзадач, в свою очередь, может быть разбита на еще более простые подзадачи, и т.д. Если задача в ходе такого последовательного разбиения свелась (необязательно за один шаг) сама к себе самой, имеет место рекурсия.

Если задача сводится к себе, и еще раз к себе, и так далее, то количество обращений к себе должно быть конечным.

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

Рекурсия используется во множестве стандартных алгоритмов. Далее, в курсе лекций, тема «Рекурсивные алгоритмы» будет возобновляться многократно.

Пример.

Применяя сведение задачи к себе n раз, можно «дойти» до тривиального случая – до значения 0!, а оно равно 1.

Пример 2.

Применение такого сведения задачи к себе приводит к «зацикливанию».

Числа Фибоначчи выражаются сами через себя при , но выражаются явно (дают тривиальный случай) при и :

, , , .

, – Golden Ratio.

Сумма убывающей геометрической прогрессии

, ,

есть функциональный (а именно, степенной, по степеням переменной ) ряд с коэффициентами 1, 1, ….

Полиномы Фибоначчи являются коэффициентами разложения в степенной ряд функции

, .

Полиномы Фибоначчи выражаются «сами через себя» при , но выражаются явно (дают тривиальный случай) при и :

, ,

Связь с числами Фибоначчи:

T_EX (Дональд Кнут)

Пример рекурсивной функции

function Fib(n: integer; x: double): double;

Дата добавления: 2014-01-06