Пример программы с использованием рекурсии

Program Arsac;
Var first: word;
Procedure posledov (i: word);
Begin
Writeln (i);
If i=1 then exit;
If odd(i) then posledov(3*i+1) else posledov(i div 2);
End;
Begin
Write (‘ введите первое значение ’); readln (first);
Posledov (first);
Readln;
End.

Виды рекурсий

1. Простая а) Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией. б) Если в процедуре рекурсивный вызов не является завершающей инструкцией, то такая рекурсия называется вложенной.

2. Сложная или косвенная:Функция A вызывает функцию B, а функция B — функцию A.

Рекурсия и цикл

Что такое цикл?
Цикл – разновидность управляющей конструкции. Управляет она, очевидно, выполнением кода (как например, конструкция if (условие) [ then ] оператор, где оператор выполняется, только если условие истинно).
Цикл состоит из двух частей: условия и тела цикла. Циклы, как и многое другое, можно классифицировать по разным признакам. В частности, существуют циклы с предусловием и постусловием, безусловные, вложенные и т.д. Простейшим из них является цикл с предусловием, т.к. в нем тело цикла (тело цикла – это набор операторов) выполняется только в случае истинности условия.
На псевдокоде цикл с предусловием обычно обозначается так:
while (условие) do {оператор1; оператор2; … } Здесь в круглых скобках записано условие цикла, а в фигурных – тело цикла.
Например, так можно распечатать все числа от nдо 1:
while (n > 0) do { // на каждом шаге цикла проверяем, не стало ли n <= 0, т.е. не выполнилось ли условие выхода из цикла print(n); // печатаем текущее значение n n = n — 1; // уменьшаем значение n, чтобы оно в конце концов стало меньше 0 и мы вышли из цикла }

Этот фрагмент кода делает следующее: на каждом шаге цикла сначала проверяется условие, что n > 0, т.к. если оно не выполнено, нам будет необходимо прекратить выполнение дальнейших действий, связанных с поставленной задачей. Если условие оказалось ложно, т.е. n уже меньше либо равно нулю, тело цикла не выполняется и работа этого кода заканчивается. Если же оно окажется истинно, и n все еще больше нуля, т.е. его можно печатать, то выполняется тело цикла: n печатается и уменьшается на единицу, чтобы перейти к следующему значению n. Затем снова выполняет проверка условия, т.е. делается следующий шаг цикла.
При чем здесь рекурсия?
выполнение нового шага цикла – это выполнение точно такой же операции, как та, что выполнялась только что. Т.е. как будто в конце каждого шага цикл снова вызывает выполнение самого себя.
Реализация этой операции в виде рекурсивной функции может иметь следующий вид:
dec_print(n) { if (n > 0) then { // проверка условия, как в цикле print(n); // печать очередного значения n dec_print(n-1); // вызов функции от следующего значения n } }

На каждом шаге рекурсии проверяется условие n > 0. Если оно не выполнится, ничего больше происходить не будет, т.к. нет ветки else, точно так же, как и в цикле. Если же оно истинно, будут выполнены операторы во вторых фигурных скобках: сначала напечатано очередное значение n, а потом вызвана та же функция от уменьшенного значения n – последнее равносильно выполнению оператора n = n — 1; в цикле и переходу к следующему шагу. Этот вызов функции снова запустит выполнение аналогичных действий: сначала проверка истинности условия, а затем выполнение действий в зависимости от результатов проверки. Заметим, все ровно так же, как и в цикле, только записано иначе, но все равно очень похоже.
Теперь попробуем задать такое преобразование в общем виде. Цикл с предусловием, как сказано выше, имеет следующий вид:
while (условие) do {оператор1; оператор2; … }

Его можно заменить такой рекурсивной функцией:
cycle(...) { // параметры зависят от того, что происходит в цикле if (условие) then { // проверка такого же условия, как в цикле оператор1; // операторы из тела цикла оператор2; … cycle(...); // рекурсивный вызов функции } }

При этом рекурсивный вызов функции происходит с уже другими значениями параметров, чтобы выполнение когда-нибудь завершилось, т.е. выполнилось условие выхода из рекурсии.
7. Понятие выражения, операции, операнда. При выполнении программы осуществляется обработка данных, в ходе которой с помощью выражений вычисляются и используются различные значения. Выражение представляет собой конструкцию, определяющую состав данных, операции и порядок выполнения операций над данными. Выражение состоит из операндов, знаков операций и круглых скобок. В простейшем случае выражение может состоять из одной переменной или константы. Тип значения выражения определяется типом операндов и составом выполняемых операций. Операнды представляют собой данные, над которыми выполняются действия. В качестве операндов могут использоваться константы, переменные, элементы массивов и функции. Операции – это действия, которые выполняются над операндами. Операции бываю унарными и бинарными. Унарная операция относится к одному операнду, и ее знак записывается перед операндом, например, - x. Бинарная операция выражает отношение между двумя операндами, и знак ее записывается между операндами, например, x + y. Круглые скобки используются для указания порядка выполнения операций. Если в операциях используется несколько данных, то их типы должны быть либо идентичными, либо совместимыми.В зависимости от типов операций и операндов выражения могут быть арифметическими, логическими и строковыми. Арифметические выражения (АВ). Результатом выполнения АВ является число, тип которого зависит от типов операндов, составляющих это выражение. В АВ можно использовать числовые типы (целочисленные и вещественные), арифметические операции и функции, возвращающие числовое значение. Тип значения АВ определяется типом операндов и операциями. Если в операции участвуют целочисленные операнды, то результат операции также будет целочисленного типа. Если хотя бы один из операндов принадлежит к вещественному типу, то результат также будет вещественным. Исключением является операция деления, результат которой всегда вещественный.

Унарные арифметические операции + (Сохранение знака) и – (Отрицание знака) относятся к знаку числа и не меняют типа числа.

Примеры. Пусть в программе есть строки: var a, b, c, d: integer; x, y: real;... a:=40; b:=13; c:= a div b; d:= a mod b; //c=3, d=1 y:=sin(a) + b/exp(x) - 12.5; // y=sin a + b/ e ^x – 12,5 Над данными целочисленного типа можно выполнять также следующие побитовые (поразрядные) операции: o Shl – сдвиг влево; o Shr – сдвиг вправо; o And – И (арифметическое умножение); o Or – ИЛИ (арифметическое сложение);o Xor – арифметическое исключающее ИЛИ; o Not – Не (арифметическое отрицание). Особенностью побитовых операций является то, что они выполняются над операндами поразрядно. Примеры. Пусть в программе есть строки: var a, b, c, d: integer;... a:=5; b:=9; c:= Not a; // a= 0101, Not (0101) = 1010 =10 _дес. d:= a And b; // b=1001, 0101 And 1001 = 0001 = 1 _дес. Логические выражения (ЛВ). Результатом выполнения ЛВ является логическое значение True или False. Такие выражения чаще всего используются в условных операторах и операторах цикла. Логические выражения могут содержать: o логические константы True и False; o логические переменные типа Boolean; o операции сравнения (отношения); o логические операции; o круглые скобки. Для установления отношения между двумя значениями, заданными выражениями, переменными или константами, используются следующие операции сравнения: =, <, >, <=, >=, <>. Операции сравнения выполняются после вычисления соответствующих выражений. Результатом операции сравнения является значение False, если соответствующее отношение не имеет место, и значение True в противном случае. Результат выполнения логических операций при применении их к логическим выражениям (операндам логического типа) будет логического типа (Boolean). Логические операции And, Or, Xor являются бинарными, операция Not – унарной.

8)Понятие типы данных»