Рекурсия
СодержаниеРекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6Рекурсия. Рекурсией называется ситуация, когда процедура или функция сама себя вызывает. Вот типичная конструкция такого рода:procedure proc(i:integer);begin anweisungen1; if bedingung then proc(i+1); anweisungen2;end;Вызов proc(1) означает, что proc вызывает себя раз за разом с помощью proc(2), proc(3),.. до тех пор, пока условие bedingung не отменит новый вызов. При каждом вызове выполняется оператор anweisungen 1, после чего порядок выполнения операторов прерывается новым вызовом proc(i+1). Чтобы для каждого вызова был отработан и оператор anweisungen2, все локальные переменные процедуры сохраняются в стеке. Стеком является структура магазинного типа LIFO (Last In First Out), т.е. если, например, при proc(10) условие более не выполняется, anweisungen2 выполняется со значениями, обрабатываемыми в обратном порядке для proc(9),…,proc(1). Локальные параметры помещаются в стек один за другим и выбираются из стека в обратной последовательности (латинское recurrere означает «возвращение назад»). В Паскале можно пользоваться именами лишь тогда, когда в тексте программы этому предшествует их описание. Рекурсия является единственным исключением из этого правила. Имя proc можно использовать сразу же, не закончив его описания. Пример1 представляет собой бесконечную рекурсию, с помощью которой можно установить, насколько велик стек. При этом помните, что при использовании директивы (*$S+*) при переполнении стека получим сообщение об ошибке; а при использовании директивы (*$S-*) – нет, а значит, мы скорее всего столкнемся с зависанием системы. Установкой по умолчанию является (*$S+*). Программа будет прервана с выдачей сообщения об ошибке «Error 202: stack overflow error (“Ошибка 202: переполнение стека»).Пример1:Program stack_test; {программа проверки стека}procedure proc(i:integer);begin if i mod 1024 = 0then writeln(i:6); proc(i+1);end;begin proc(1);end. Стек связан с другой структурой памяти – с динамической областью. С помощью директивы (*$М*) можно управлять размером стека. Рекурсия не должна восприниматься как некий программистский трюк. Это скорее некий принцип, метод. Если в программе нужно выполнить что-то повторно, можно действовать двумя способами:- с помощью последовательного присоединения (или итерации в форме цикла);- с помощью вложения одной операции в другую (а именно, рекурсий). В следующем примере2 один раз счет от 1 до n ведется с помощью цикла, а второй – с помощью рекурсии. При этом хорошо видно, как заполняется, а затем освобождается стек. В процедуре rekursion операция writeln(i:30) выполняется перед рекурсивным вызовом, после чего writeln(i:3) освобождает стек. Поскольку рекурсия выполняется от n до 1, вывод по команде writeln(i:30) выполняется в обратной последовательности n,n-1,…,1, а вывод по команде writeln(i:3) – в прямой последовательности 1,2,…,n (согласно принципу LIFO – последним пришел, первым обслужен).Пример2: Показывает принципиальное различие между итерацией и рекурсией: итерации необходим цикл и локальная переменная k как переменная цикла. Рекурсии ничего этого не требуется!program iterativ_zu_rekursion; var n:integer;procedure rekursion (i:integer);begin writeln(i:30); if...
Другие файлы:
Рекурсия и функции
Определение функции, ее прототип. Рекурсия - частичное определение объекта через себя. Рекурсивная функция произведения 2-х целых чисел. Задача о вычи...
Информатика. Творчество. Рекурсия.
Программирование на языке Паскаль
Понятие программы и ее основные составляющие. Операторы ввода и вывода. Разветвляющиеся алгоритмы. Цикл как многократное выполнение одинаковых действи...
Финансовые функции и рекурсия
Вычисление значений финансовых функций с помощью электронных таблиц Excel или других прикладных программ. Рекурсивные методы решения прикладных задач,...
