Скачать программы Все программы автора1. 12. 2. Рекурсивные функции и процедурыЕсли одна процедура (Pr_2) вызывает в своем разделе выполнения другую (Pr_1), то вызываемая процедура должна быть описана во внешней программе перед описанием вызывающей процедуры, либо внутри вызывающей процедуры. Возможны и циклические случаи: если процедура вызывает сама себя - прямая рекурсия , если обе процедуры вызывают в своих разделах выполнения друг друга - косвенная рекурсия.
Если процедура вызывает сама себя ( прямая рекурсия ), то она описывается как обычно. Рекурсия традиционно применяется для итерационного расчета значения функции с использованием результатов предыдущего шага. Например, для расчета выражений вида: X! ( X факториал ), X N ( X в степени N ), вычисляемых по формулам: X N = X N - 1 * k , где k - постоянная или переменная величина. В общем случае рекурсия применяется при расчете функции от функции: F N (x) = F N - 1 (x). При этом процесс происходит в два этапа: обратное движение с запоминанием цепочки расчета в оперативной памяти и прямое движение - расчет с использованием полученной цепочки. Рекурсивные процедуры требуют больше памяти для запоминания промежуточных результатов, чем обычные циклические операторы, поэтому рекурсии используются реже. В случае рекурсивных процедур следует обязательно предусмотреть условие окончания вызова процедуры. Приведем пример традиционного использования рекурсии. Пусть требуется рассчитать число осколков, полученных в результате деления тела за "N" миллисекунд, если каждый осколок делится на два за одну миллисекунду. Тогда при N=0 число осколков = 1, при N>0 число осколков = 2 N = 2 * 2 (N - 1) .
Функция, возвращающая число осколков, будет иметь вид:
Function K_O(N: word): Longint; begin if N=0 then K_O:=1 {условие окончания рекурсии} else K_O:=2 * K_O(N-1) {рекурсивный вызов} end; Пример функции, возвращающей число осколков, без использования рекурсии: Function K_O(N: word): Longint; var N_1: Longint; i: word; begin N_1:=1; for i:=1 to N do N_1:= 2 * N_1; K_0:= N_1 end; Если к каждому осколку добавляется два осколка, то число осколков = (1+2) N = 3 * 3 (N - 1) . Во внешней программе число осколков (переменная "NN") расчитывается вызовом функции: NN:= K_O(t); где t - значение фактического параметра времени.
Практическое задание N 1. 31
Написать и отладить программы с использованием функций: 1. Рассчитать число зерен, выращенных крестьянином за "N" лет, если он посадил 10 зерен, а годовой урожай составляет 22 зерна на каждое посаженное зерно. 2. Рассчитать число рыбок - самок, выращенных в аквариуме за "N" месяцев, если вначале была одна самка, а ежемесячный прирост от одной самки составляет три самки, причем все рыбки остаются живые. 3. Рассчитать число золотых монет, принесенных в дань господину, если "N+1" подданных последовательно передают монеты от первого к последнему. Причем, первый отдает одну монету, второй увеличивает число монет вдвое, третий - в три раза и т. д. 4. Рассчитать число рыбок, выращенных в аквариуме за "N" лет, если вначале было две рыбки, а число рыбок увеличивается пропорционально числу лет, т. е. 4, 12, 48 и т. д. 5. Рассчитать функцию y=sin(sin(sin(. . . (sin(x))))), в которой имя функции "sin" повторяется N раз. 6. Рассчитать функцию y=a/(b+(a/(b+(a/(b+(. . . +a/b)))))), в которой знак деления "/" повторяется N раз. Примечание: написать функцию для расчета с использованием прямой рекурсии и без рекурсивного вызова. Если обе процедуры вызывают в своих разделах выполнения друг друга ( косвенная рекурсия ), то каждая из процедур должна быть описана ранее другой, что невозможно. В этом случае в разделе описания основной программы используется предварительное описание одной из процедур: пишется только заголовок процедуры и служебное слово Forward. Далее приводится полное описание второй процедуры, а затем полное описание первой процедуры (причем, второй раз в заголовке процедуры список формальных параметров можно не указывать).
Приведем пример использования рекурсии:
Program Rek; {раздел описания основной программы} {---------- ----------------------------------------------------------- } Procedure pr_1(i:word); Forward; {предварительное описание процедуры pr_1} { ----------------------------------------------------------------- } Procedure pr_2; {полное описание процедуры pr_2} var ch: char; i: word; begin Writeln('Купите десять билетов - выиграете миллион !'); Writeln(' Нажмите "Y" или "N"'); Readln(ch); i:=10; if( ch='Y') or ( ch='y') then Pr_1(i) { вызов процедуры } else Halt end; { ----------------------------------------------------------------- } Procedure pr_1; { полное описание процедуры pr_1} var n, n1: integer; begin if i=10 then begin Randomize; n1:= Random(900)+100 end; if (i = 0) then Pr_2 {условие окончания прямой рекурсии} else begin repeat writeln('введите трехзначный номер билета'); Readln(n) until (n<1000) and (n>99); if (n<>n1) then begin writeln(' билет без выигрыша '); writeln('осталось ', i-1, 'билетов'); Pr_1(i-1) {прямая рекурсия} end else begin Writeln('Вы угадали, получите выигрыш в банке!'); Pr_2 {косвенная рекурсия} end end; { ----------------------------------------------------------------- } BEGIN PR_2 {раздел выполнения основной программы} End.
Здесь процедура Pr_1 при первом вызове инициирует случайное трехзначное число "n1" - выигрышный номер. При каждом вызове процедура Pr_1 запрашивает ввод трехзначного номера билета "n". Если номер билета не совпал (n<>n1) и остались еще билеты (i<>0), то снова вызывается процедура Pr_1, иначе вызывается процедура Pr_2 (окончание рекурсивного вызова). Если номера совпали (n1=n), то выводится сообщение: 'Вы угадали, получите выигрыш в банке!'. Процедура Pr_2 либо вызывает процедуру Pr_1, либо программа заканчивается (оператор Halt). В процедуре Pr_2 заголовок не имеет параметров, а в процедуре Pr_1 параметры указываются при первом описании. В данном случае приводится управляемая на каждом шаге рекурсия (процедура запрашивает номер билета). Включив тело процедуры Pr_2 в Pr_1 и введя операторы цикла, нетрудно избавиться от рекурсивного вызова процедур.
Практическое задание N 1. 32
Написать и отладить программу с рекурсивным вызовом процедур: Ученики двух групп имеют порядковые номера от 1 до N в каждой группе. В процедуре P_1 функцией Random определяются два числа "a" и "b" от 1 до N. Если числа разные, то два участника с номерами "a" и "b" выбывают, оставшиеся ученики перенумеровываются от 1 до (N - 1) и играют дальше (процедура P_1 повторяется с новыми значениями "a" и "b"), иначе выводится значение совпавшего номера, ученики получают приз и процедура P_2 предлагает играть снова. |