Использование рекурсивных процедур кратко

Обновлено: 05.07.2024

Рекурсия - это способ организации вычислительного процесса, при котором процедура или функция в процессе выполнения входящих в ее состав операторов обращается сама к себе непосредственно, либо через другие процедуры и функции.

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

Рассмотрим пример. Вычислить значение F=M! Рекурсивное определение значение факториала можно записать следующим образом: при М=1 F=1 ; при М> 1 F= M!= M*(M-1)!, т.е. М! определяется через (М-1)!

a) Рекурсивная функция

PROGRAM MAIN;

VAR M: INTEGER;

FUNCTION FACT (N:INTEGER): REAL;

FACT:= N* FACT(N-1);

WRITELN (' M!=', F);

b) Рекурсивная процедура

VAR M: INTEGER;

PROCEDURE FACT(N:INTEGER; VAR F: REAL);

VAR Q : REAL;

IF N=1 THEN Q:=1

ELSE FACT(N-1,Q);

WRITELN (' M!=', F);

B варианте а) при м=4 выполняются следующие действия: FACT:=4*FACT(3); FACT:=3*FACT(2); FACT:=2*FACT(1); FACT(1):=1.

При входе в функцию в первый раз отводится память под локальную переменную, соответствующую параметру-значению; ей присваивается значение фактического параметра (М). При каждом новом обращении строятся новые локальные переменные. Так как FACT(1)=1, то выполнение функции заканчивается. После этого выполняются действия: FACT(1):=1; FACT:=2*FACT(1); FACT(2):=2; FACT:=3*FACT(2); FACT(3):=3*2=6; FACT:=4*FACT(3); т.е. FACT=24.

Область действия (видимости) имен. Глобальные и локальные переменные. Достоинства и недостатки использования глобальных переменных и параметров при обмене информацией между программами. Рекомендации по применению

Любая подпрограмма представляет собой блок со своей областью описаний. Она может содержать внутри этого блока описания других процедур и функций, а также обращения к ним. Объекты, описанные внутри какого-либо блока, являются по отношению к нему локальнымии не доступны внешним блокам. На них можно ссылаться тольковнутри блока, в котором они описаны. Под объектами понимаются имена констант, типов, переменных, процедур, функций. Объекты, описанные во внешних блоках и не описанные во внутренних, являются глобальными по отношению к внутренним и доступны как во внешнихблоках, так и во внутренних. При совпадении имен глобальных и локальных переменных, локальные переменные отменяют действия глобальных в пределах области своего действия.

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

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

Достоинства и недостатки глобальных переменных:

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

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

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

10. Запись как тип данных. Работа с записями: описание записи, оператор присоединения, запись с вариантами. Использование записей

Запись– это структура данных, состоящая из фиксированного числа компонент, называемых полями. Каждое поле имеет свой идентификатор и тип. К компонентам записи возможен прямой доступ и они могут выборочно обновляться. Идентификатор в самой записи должен быть уникальным. Для обращения к отдельным полям записи указываются составные имена: имя записи, после которого ставится точка и записывается идентификатор поля. Запись можно передавать в качестве параметра процедуры или функции, но значением функции запись быть не может.

В общем виде описание типа для записи можно представить:

TYPE = RECORD

TYPE TA= RECORD

VAR A: ARRAY[1..10] OF TA;

Здесь описан одномерный массив, каждый элемент которого представляет собой запись, имеющую структуру типа TA.

Запись может объявляться и непосредственно в разделе описания переменных.

VAR C : RECORD

При обращении к компонентам записи используются составные имена. Для сокращения имен и повышения удобства работы с записями применяется оператор присоединения WITH.

Тогда в операторе при ссылке на компоненты записи имя переменной можно опускать.

Состав и структура записи могут динамически меняться в зависимости от значения какого-либо из своих полей, называемого полем- признаком.

В общем виде описание записи с вариантами выглядит так:

TYPE = RECORD

Метки варианта должны иметь такой же тип, как у селектора.

Если какой-либо метке варианта не соответствуют поля, то записываются пустые круглые скобки.

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

- для студентов поля: номер группы и специальность;

- для преподавателей: институт, кафедра, стаж работы;

- для сотрудников дополнительных полей нет.

Описание соответствующей записи структуры данных:

TYPE TZ=RECORD

CASE N:CHAR OF

‘P’: ( IN:BYTE; KAF:STRING; ST:BYTE );

‘S’: ( NG:BYTE; SP:INTEGER );

Файлы в Паскале. Понятие физического и логического файла, соотношение между ними. Типы файлов и их описание, стандартные процедуры и функции для работы с файлами. Общие характеристики методов доступа к файлам

При обработке на компьютере информация может храниться на внешних носителях в виде файлов.

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

Физическая запись– это совокупность данных, передаваемых в прямом или обратном направлении при одном обращении к внешнему носителю (т.е. минимальная единица обмена данными между внешней и оперативной памятью. С физическими записями - блоками работает операционная система). Физическая запись состоит из логических записей.

Для обращения к записям файла на внешнем носителе используется понятие логического файла.

Логический файлили файл в программе – это совокупность данных, состоящая из логических записей, объединенных общим назначением.

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

− Число записей в файле произвольно.

− В каждый момент времени доступна только одна запись.

− Длиной файла называют количество записанных компонентов. Файл, не содержащий записей, называется пустым.

Стандартные средства обеспечения взаимодействия между логическим и физическим файлом:

1) установление связи между физическим и логическим файлами ASSIGN (…), где указывается имя файла в программе и имя файла на внешнем носителе (без контроля существования файла);

2) обеспечение физической возможности обмена информацией между файлами, открытие файла для чтения информации из него RESET (…) или для записи в него REWRITE (…). При этом осуществляется контроль наличия физического файла;

3) прекращение, отмена возможности физического обмена информацией между файлами, закрытие файла CLOSE (…). Связь между файлами при этом не разрывается (т.е. ASSIGN действует).

При работе с файлами необходимо придерживаться следующих общих правил:

- каждый файл в программе (переменная файлового типа) должен быть объявлен в разделе VAR. Не допускается использование таких переменных в выражениях и операторах присваивания. Тип компонентов файла может быть любым, кроме файлового.

- каждый файл в программе должен быть закреплен за конкретным файлом на носителе процедурой ASSIGN;

- открытие существующего файла для чтения, корректировки или дозаписи производится процедурой RESET, открытие создаваемого файла для записи – процедурой REWRITE;

- по окончании работы с файлом он должен быть закрыт процедурой CLOSE.

Процедуры и функции для работы с файлами.

ASSIGN (имя_файла_в_программе, имя_файла_на_носителе) –процедура устанавливает связь между файловой переменной(имя_файла_в_программе) и файлом на носителе. Здесь:

имя_файла_в_программе - это файловая переменная, т.е. идентификатор, объявленный в программе как переменная файлового типа.

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

RESET (имя_файла_в_программе) –процедура открытия существующего файла

− для чтения при последовательном доступе и

− для чтения и записи при прямом доступе.

Указатель файла при этом устанавливается на первую запись (с 0 номером). Если файл с таким именем не существует, то происходит аварийное завершение программы.

REWRITE (имя_файла_в_программе) –процедура открытия создаваемого файла для записи. Если файл с таким именем не существовал, то он создается и начинается заполнение файла. Если файл с таким именем уже существовал, то он стирается, и заполнение файла начинается заново. Указатель файла устанавливается на первую запись (запись – она жекомпонент файла).

READ(имя_файла_в_программе, имя_переменной) –процедура чтения очередного компонента файла в переменную, тип которой должен совпадать с типом компонентов файла.

READLN(имя_файла_в_программе, имя_переменной) применяется для чтения записей из текстового файла.

WRITE(имя_файла_в_программе, имя_переменной

[,имя_переменной…] );

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

WRITELN (имя_файла_в_программе, имя_переменной) – применяется для записи компонента в текстовый файл.

SEEK (имя_файла_в_программе,номер_компонента) – процедура установки текущего указателя для чтения или записи требуемого компонента файла.

CLOSE (имя_файла_в_программе) –процедура закрытия файла. Обязательно должна использоваться после окончания работы с файлом, в особенности после создания файла, иначе может произойти потеря данных, находящихся в последнем буфере. В одной программе файл может быть открыт и закрыт несколько раз с разными назначениями.

FILEPOS (имя_файла_в_программе) –функция определения номера текущей записи файла.

FILESIZE (имя_файла_в_программе) –функция определения общего количества записей файла.

EOF (имя_файла_в_программе) –функция определения признака конца файла (End Of File). Получает значение TRUEпри чтении последней записи файла.

EOLN (имя_файла_в_программе) –функция обнаружения конца строки в текстовом файле (End Of Line). Имеет значение TRUE,если найден конец строки.

IORESULT –функция возврата условного признака последней операции ввода-вывода. Если операция завершилась успешно, функция возвращает нуль. Функция становится доступной только при отключенном автоконтроле ошибок ввода-вывода. Директива компилятора отключает, а – включает автоконтроль ошибок. Если автоконтроль отключен и операция ввода-вывода привела к возникновению ошибки, все последующие обращения к вводу-выводу блокируются, пока не будет вызвана функция IORESULT.Функция, как правило, применяется для контроля существования файла, с которым предстоит работать.

ERASE (имя_файла_в_программе)– процедура уничтожения файла. Открытый файл прежде должен быть закрыт (используется модуль DOS).

RENAME (старое_ имя_файла_на_носителе, новое_имя_файла_на_носителе) –процедура для переименования файла. Используется после закрытия файла (используется модуль DOS).

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

Рекурсивностью в Паскале могут обладать как функции, так и процедуры.

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

Поэтому важно: На каждом шаге выполнения рекурсивного тела процедуры или функции обязательно либо изменение параметра данной функции, либо наличие условия, при котором она больше себя не будет вызывать!

Рассмотрим простой пример использования рекурсивной процедуры:

Пример: Напечатать последовательность чисел в обратном порядке, используя рекурсивный вызов процедуры. Например:
row (5) = 5 4 3 2 1
Из условия задачи ясно, что условием завершения рекурсии будет сам аргумент функции, который следует уменьшать на единицу, пока он >= 1 .

procedure row(n:integer); begin if n >=1 then begin write (n, ' '); row(n-1) end; end; begin row(10); end.

Теперь рассмотрим более сложный пример использования рекурсии в Паскаль.

Пример: Написать рекурсивную процедуру, выводящую цифры, переданного ей в качестве фактического параметра числа, в обратном порядке.

Например: при переданном функции числе 3078 , должно в итоге вернуть 8703
Использовать операции div и mod.

procedure reverse (n: integer); begin write (n mod 10); if (n div 10) <> 0 then reverse(n div 10) end; begin writeln; reverse(3078); end.

А теперь посмотрим, как используется рекурсия при вычислении факториала в Паскаль.

Подсказка:
2!=2*1=2
3!=3*2*1=6
Выводим формулу a!=a*((a-1)!)

var x: integer; function fact (a: integer): integer; begin if (a sumTo(n) , которая для данного n вычисляет сумму чисел от 1 до n , например:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
.

Рекурсия: Написать рекурсивную функцию определения степени числа.

var x,y: integer; function stepen (a,b: integer):integer; var . begin . end; begin writeln('число?'); readln(x); writeln('степень?'); readln(y); writeln(stepen(x,y)); end.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365	3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток	1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление	700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление	665 mod 35 = 0
остаток нуль	НОД равен 35

Рекурсия: Распечатать первые 10 чисел Фибоначчи (до 21), используя рекурсивную процедуру с двумя параметрами.
Результат должен быть: 1 2 3 5 8 13 21 34 55 89
Дополните код:

procedure fib (i,n: integer); begin writeln (i+n,' '); if . then fib(. ) end; begin fib(0,1); end.

Потренируйтесь в решении задач по теме, щелкнув по пиктограмме:

Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.

Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции.

Для рекурсии в её наиболее общей, неитеративной форме типична необходимость отсрочки некоторых действий; см., в частности, пример (4). По этой причине она вряд ли показана для забывчивых людей, но вполне пригодна для подходящим образом оборудованных машин. Повторение же — это в значительной степени наш повседневный опыт. см. 3, 4, 6. Бауэр Гооз

3.2. Примеры

Пример 1. Вспомним определение натуральных чисел. Оно состоит из двух частей:

1. 1 — натуральное число;

2. если n — натуральное число, то n + 1 — тоже натуральное число.

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

Пример 2 . Похожим образом задаются числа Фибоначчи: первые два числа равны 1, а каждое из следующих чисел равно сумме двух предыдущих:

Пример 3. Популярные примеры рекурсивных объектов — фракталы. Так в математике называют геометрические фигуры, обладающие самоподобием. Это значит, что они составлены из фигур меньшего размера, каждая из которых подобна целой фигуре. На рисунке 8.2 показан треугольник Серпинского — один из первых фракталов, который предложил в 1915 г. польский математик В. Серпинский. Рис. 8.2

Равносторонний треугольник делится на 4 равных треугольника меньшего размера (см. рис. 8.2, слева), затем каждый из полученных треугольников, кроме центрального, снова делится на 4 еще более мелких треугольника и т. д. На рисунке 8.2 справа показан треугольник Серпинского с тремя уровнями деления.

Пример 4. Ханойские башни.

Согласно легенде, конец света наступит тогда, когда монахи Великого храма города Бенарас смогут переложить 64 диска разного диаметра с одного стержня на другой. Вначале все диски нанизаны на первый стержень. За один раз можно перекладывать только один диск, причём разрешается класть только меньший диск на больший. Есть также и третий стержень, который можно использовать в качестве вспомогательного (рис. 8.3).

Решить задачу для 2, 3 и даже 4 дисков довольно просто. Проблема в том, чтобы составить алгоритм для любого числа дисков.

Пусть нужно перенести n дисков со стержня 1 на стержень 3. Представим себе, что мы как-то смогли переместить n – 1 дисков на вспомогательный стержень 2. Тогда остается перенести самый большой диск на стержень 3, а затем n — 1 меньших дисков со вспомогательного стержня 2 на стержень 3, и задача будет решена. Получается такой псевдокод:

перенести ( n -1, 1, 2)

перенести ( n -1, 2, 3)

Процедура перенести (которую нам предстоит написать) принимает три параметра: число дисков, начальный и конечный стержни. Таким образом, мы свели задачу переноса n дисков к двум задача переноса n – 1 дисков и одному элементарному действию — переносу 1 диска. Заметим, что при известных номерах начального и конечного стержней легко рассчитать номер вспомогательного, так как сумма номеров равна 1 + 2 + 3 = 6. Получается такая (пока не совсем верная) процедура:

алг Hanoi (цел п, к, m )

р:=6-к-т Hanoi ( n -1, k , p )

вывод k , ' -> ', m , нс

Hanoi ( n -1, p , m )

Эта процедура вызывает сама себя, но с другими значениями параметров. Такая процедура называется рекурсивной.

Основная программа для решения задачи, например, с четырьмя дисками будет содержать всего одну строку (перенести 4 диска со стержня 1 на стержень 3):

Очевидно, что если нужно переложить 0 дисков, задача уже решена, ничего перекладывать не надо. Это и есть условие окончания рекурсии: если значение параметра п, переданное процедуре, равно 0, нужно выйти из процедуры без каких-либо действий. Для этого в школьном алгоритмическом языке используется оператор выход (в Паскале — оператор exit ). Правильная версия процедуры выглядит так:

алг Hanoi (цел n , к, m )

если п=0 то выход

procedure Hanoi (n,k,m:integer);

if n=0 then exit;

Чтобы переложить N дисков, нужно выполнить 2 N — 1 перекладываний. Для N = 64 это число равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, каждую секунду перемещали один диск, им бы потребовалось 580 миллиардов лет.

Стандартный алгоритм перевода числа в двоичную систему можно записать, например, так:

нц пока п<>0

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

Однако можно применить красивый подход, использующий рекурсию. Идея такова: чтобы вывести двоичную запись числа n , нужно сначала вывести двоичную запись числа div ( n , 2), а затем последнюю цифру — mod ( n , 2). Если число-параметр равно нулю, нужно выйти из процедуры.

Такой алгоритм очень просто программируется:

алг printBin (цел n )

если п=0 то выход все

procedure printBin(n:integer);

if n=0 then exit;

printBin(n div 2);

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

Пример 6 . Составим функцию, которая вычисляет сумму цифр числа. Будем рассуждать так: сумма цифр числа n равна значению последней цифры плюс сумма цифр числа div ( n , 10) . Сумма цифр однозначного числа равна самому этому числу, это условие окончания рекурсии. Получаем следующую функцию:

алг цел sumDig( цел n)

знач:= знач + sumDig ( div ( n ,10))

var sum: integer;

sum:=sum+sumDig (n div 10);

Пример 7 . Алгоритм Евклида, один из древнейших известных алгоритмов, предназначен для поиска наибольшего общего делителя (НОД) двух натуральных чисел. Формулируется он так.

Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

Этот алгоритм может быть сформулирован в рекурсивном виде. Во-первых, в нём для перехода к следующему шагу используется равенство НОД( a , b ) = НОД(а – b , b ) при а ³ b . Кроме того, задано условие останова: если одно из чисел равно нулю, то НОД совпадает со вторым числом. Поэтому можно написать такую рекурсивную функцию:

алг цел NOD( цел a, b)

если а=0 или b =0 то

иначе знач :=N0D(a, b-a)

function NOD(a, b:integer):integer

if (a=0) or (b=0) then begin

else NOD:=NOD(a, b-a)

Заметим, что при равенстве одного из чисел нулю второе число совпадает с суммой двух чисел, поэтому в качестве результата функции принимается а + b .

Существует и более быстрый вариант алгоритма Евклида (модифицированный алгоритм), в котором большее число заменяется на остаток от деления большего числа на меньшее.

Рассмотрим ещё несколько алгоритмов, которые можно реализовать с помощью рекурсии:

1. Алгоритм сложения двух положительных десятичных чисел.

Этот алгоритм запёчатлён в наших мозгах с начальной школы; обычно мы исполняем его наполовину бессознательно. Сложность алгоритма мы замечаем только тогда, когда пытаемся явно описать эту хорошо знакомую нам процедуру.

В данном случае количество элементарных тактов обработки зависит от разрядности большего слагаемого.

2. Алгоритмы разложения натурального числа на простые множители.

Если в нашем распоряжении имеется достаточно длинная таблица простых чисел, то можно пытаться последовательно делить заданное число на 2, 3, 5, 7, . — не разделится ли без остатка,— пока, наконец, не придём к 1.

Если же таблицы простых чисел в распоряжении нет, то можно также последовательно пытаться делить заданное число на натуральные числа 2, 3, 4, 5, 6, 7. до тех пор, пока не останется 1; при этом для каждого составного числа как делителя выполняемая попытка деления будет бесполезной.

Последовательность получающихся в конечном счёте делителей даст требуемое разложение на простые множители.

В данном случае количество элементарных тактов обработки зависит от величины разлагаемого числа.

3. Алгоритм вставки карточки в (упорядоченную) картотеку (предполагается, что в картотеке нет рейтера – зажима для удобства отыскания картотечных карточек).

В данном случае количество элементарных тактов обработки зависит от размера картотеки

4. Алгоритм сортировки (несортированной) картотеки.

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

Этот пример демонстрирует иерархическую структуру: алгоритм сортировки основан на алгоритме смешивания.

В данном случае количество элементарных тактов обработки зависит от размера картотеки.

5. Алгоритм вычисления значения дроби (а + b )/(а — b ).

Сначала вычисляем (используя алгоритмы сложения и вычитания) значения выражений а + b и а — b (все равно, последовательно или одновременно, поскольку ситуация здесь совместная), а потом образуем частное от деления полученных результатов (используя алгоритм деления).

В случае общих формул обнаруживается как иерархическое строение, так и совместность.

В данном случае количество элементарных тактов обработки бесконечно.

6. Алгоритм, распознающий, можно ли получить последовательность знаков а из последовательности знаков b посредством вычёркивания некоторых знаков.

7. Алгоритм вычисления числа е (т. е. вычисления последовательности дробей — приближений для е).

Основание натуральных логарифмов е иррационально, поэтому его можно определить только с помощью бесконечной последовательности рациональных чисел, всё лучше приближающих е. По Ламберту (1766 г.) такую последовательность можно получить следующим образом.

и образовать последовательность рациональных чисел ( A_i + В _i )/(А _i -В _i ). C 71

Здесь речь идёт о незавершающемся алгоритме для вычисления вычислимого вещественного числа, опирающемся на алгоритм из пункта 5.

В примерах 3 и 4 наличие рекурсии очевидно из самого словесного описания алгоритма.

В примере 7 речь идёт о безусловном (не зависящем от выполнения какого-либо условия) повторении.

Наряду с рекурсией и повторением в алгоритмах встречается также разбор возможных случаев. Без разбора отдельных случаев, в частности, было бы невозможно окончание рекурсивных алгоритмов.

Рассмотрим вычисление факториала N!: так называют произведение всех натуральных чисел от 1 до заданного числа N : N != 1 • 2 • 3 • . • N. Факториал может быть также введён с помощью рекуррентной формулы, которая связывает факториал данного числа с факториалом предыдущего 1 ( 1 -в математике принято, что факториал нуля равен 1. Поэтому равенство 0! = 1 можно тоже принять за базовый случай):

Здесь первая часть описывает базовый случай (условие окончания рекурсии), а вторая — переход к следующему шагу. Запишем соответствующую функцию на школьном алгоритмическом языке, добавив в начале и в конце операторы вывода:

алг цел Fact (цел N )

вывод '–> N =', N , нс

иначе знач:= N * Fact ( N -1)

вывод ' N =', N , нс

Справа от программы показан протокол её работы при вызове Fact (3) (для наглядности сделаны отступы, показывающие вложенность вызовов). Из протокола видно, что вызов Fact (2) происходит раньше, чем заканчивается вызов Fact (3). Это значит, что компьютеру нужно где-то (без помощи программиста) запомнить состояние программы (в том числе значения всех локальных переменных) и адрес, по которому нужно вернуться после завершения вызова Fact (2). Для этой цели используется стек.

Стек (англ. stack — кипа, стопка) — особая область памяти, в которой хранятся локальные переменные и адреса возврата из процедур и функций.

Один из регистров процессора называется указателем стека (англ. stack pointer , SP ) — в нём записан адрес последней занятой ячейки стека. При вызове процедуры в стек помещаются значения всех её параметров, адрес возврата и выделяется место под локальные переменные.

На рисунке 8.4, а показано начальное состояние стека, серым цветом выделены занятые ячейки. Когда функция Fact вызывается из основной программы с параметром 3, в стек записывается значение параметра, затем — адрес возврата А, и выделяется место для локальной переменной знач , в которую будет записан результат 1 ( 1 – результат функции, как правило, передаётся в вызывающую программу через регистры, но во время работы функции хранится в стеке.) (рис. 8.4, б). При втором и третьем вложенных вызовах в стек добавляются аналогичные блоки данных (рис. 8.4, в и г). Заметьте, что в нашем случае адрес возврата A_F (точка внутри функции Fact после рекурсивного вызова) в последних двух блоках будет один и тот же.

Когда выполняется возврат из процедуры, состояние стека изменяется в обратную сторону: г — в — б — а.

Что же следует из этой схемы? Во-первых, с каждым новым вызовом расходуется дополнительная стековая память. Если вложенных вызовов будет очень много (или если процедура создаёт много локальных переменных), эта память закончится, и программа завершится аварийно.

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

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

¾ часто при этом программа усложняется и становится менее понятной;

¾ нерекурсивная версия нередко требует дополнительного расхода памяти.

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

нц для i от 1 до N

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

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

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

Рекурсивная процедура вызывает саму себя. как правило, это не самый эффективный способ написания кода Visual Basic.

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

Использование рекурсивных процедур кратко

3.2. Примеры

Рекомендации по рекурсивным процедурам