Главная » Статьи » Рефераты » Без категории |
Содержание
Рекурсией называется ситуация, когда процедура или функция сама себя вызывает. Вот типичная конструкция такого рода: begin anweisungen1; anweisungen2; end; В Паскале можно пользоваться именами лишь тогда, когда в тексте программы этому предшествует их описание. Рекурсия является единственным исключением из этого правила. Имя proc можно использовать сразу же, не закончив его описания. Пример1 представляет собой бесконечную рекурсию, с помощью которой можно установить, насколько велик стек. При этом помните, что при использовании директивы (*$S+*) при переполнении стека получим сообщение об ошибке; а при использовании директивы (*$S-*) – нет, а значит, мы скорее всего столкнемся с зависанием системы. Установкой по умолчанию является (*$S+*). Программа будет прервана с выдачей сообщения об ошибке «Error 202: stack overflow error (“Ошибка 202: переполнение стека»).
Program stack_test; {программа проверки стека} begin end; begin end. Стек связан с другой структурой памяти – с динамической областью. С помощью директивы (*$М*) можно управлять размером стека. Рекурсия не должна восприниматься как некий программистский трюк. Это скорее некий принцип, метод. Если в программе нужно выполнить что-то повторно, можно действовать двумя способами: - с помощью вложения одной операции в другую (а именно, рекурсий).
Показывает принципиальное различие между итерацией и рекурсией: итерации необходим цикл и локальная переменная k как переменная цикла. Рекурсии ничего этого не требуется! program iterativ_zu_rekursion; begin end; (* Рекурсия *) bagin k :=1; while k <= i do begin k :=k+1; end; end; (* Цикл *) begin writeln; end.
Рекурсивная процедура convert переводит десятичное число z в восьмеричную систему путем деления его на 8 и выдачи остатка в обратной последовательности. Program dezimal_oktal_konvertierung; {преобразование из десятичной системы в восьмеричную} begin (* Это рекурсивный вызов *) end; begin end. Один из наиболее ярких примеров применения рекурсии дают числа Фибоначчи. Они определяются следующим образом: x[1]=x[2]=1 x[n]=x[n-1]+x[n-2] при n > 2 Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е. 1 1 2 3 5 8 13 21 34 55 … Следующий пример позволяет вычислить n-ный элемент ряда Фибоначчи как итеративно (то есть в цикле, начиная с х[1] до х[n]), так и рекурсивно (n-ный элемент ряда является суммой двух предшествующих элементов). Причем рекурсивная функция вызывает себя дважды.
С использованием рекурсии вычисляются числа Фибоначчи, причем глубина рекурсии индицируется. Перед каждым рекурсивным вызовом выводится выводиться ASCII-символ с номером 8 (Backspace), а после вызова вновь стирается. Тем самым можно наблюдать за работой программы, поскольку программа за счет delay(300) приостанавливается на 0.3 с. uses crt; begin a := 1; b := 1; then fibit :=1 for i= 3 to n do begin c :=a+b; a := b; b :=c; end; fibit :=c; end; end; begin clrscr; writeln; end. Этот пример демонстрирует прежде всего различия между итерацией и рекурсией. Итерации необходим цикл и вспомогательные величины; итерация сравнительно ненаглядна (см. fibit в приведенном выше примере). Рекурсия обходится без вспомогательных величин и обычно проще для понимания, что демонстрирует следующая запись: Итерация требует меньше места в памяти и машинного времени, чем рекурсия, которой необходимы затраты на управление стеком. Итак, если для некоторой задачи возможны два решения, предпочтение следует отдать итерации. Правда, для многих задач рекурсивная формулировка совершенно прозрачна, в то время как построение итерации оказывается весьма сложным делом. Если процедура или функция вызывает себя сама, это называют прямой рекурсией. Но может встретиться ситуация, когда процедура А вызывает процедуру В, вызывающую С, а процедура С вновь возвращается к А. В этом случаи мы имеем дело дело с косвенной рекурсией, что демонстрирует приведенный ниже пример. С таким типом рекурсии мы сталкиваемся там, где использована директива forward.
Следующая программа выдает простые числа от 1 до n, для чего используются функции next и prim, которые вызываются перекрестно, то есть рекурсивно. Одновременно это является примером применения директивы forward. program primzahlen_rekursiv_berechnen; {программа рекурсивного вычисления простых чисел} c : char; {Это прямая ссылка вперед на функцию next, которая будет определена позже} и false в противном случае} begin k :=2; while (k*k <= j) and (j mod k < > 0) do {k пробегает последовательность простых чисел, начиная с 2, вплоть до корня из j, при этом проверяется, делится ли j на одно из таких простых чисел. При этом используется следующая функция next} end {prim {Параметры уже стоят в ссылке вперед, next вычисляет, каково следующее за j простое число} begin 1 :=i+1; while not(prim(1)) do 1 :=1+1; {Итак, next вызывает в свою очередь prim} next :=1; end {next begin (******* Исполняемая часть программы *******) for i :=2 to n do begin end; end; end. | |
Просмотров: 270 | |
Всего комментариев: 0 | |