Пабочны эфект
Калі пры выкліку падпраграмы акрамя змянення параметраў-пераменных адбываюцца змяненні нейкіх глабальных аб’ектаў, то гэта называецца пабочным эфектам.
Пабочны эфект лічыцца непажаданай з’явай, бо ён можа прывесці да некантралюемасці сітуацыі. Асабліва шкодны пабочны эфект для функцыі.
Асноўнае прызначэнне функцыі – па яе параметрах атрымаць вынік. Калі пры гэтым змяняюцца глабальныя пераменныя ці параметры-пераменныя, тады змест функцыі становіцца няясным.
Прыклад 1.
PROGRAM SideEffect;
VAR k : Integer;
FUNCTION Fact (VAR n : Integer) : Longint;
VAR f : Longint;
BEGIN
f:=1;
REPEAT
f := f * n;
n := n - 1;
UNTIL n = 1;
Fact := f
END;
FUNCTION Fk(k : Integer) : Integer;
BEGIN
Fk := k;
END;
BEGIN
k := 3; Writeln (k, ' ', Fk(k) + Fact(k));
k := 3; Writeln (k, ' ', Fact(k) + Fk(k));
END;
Наша падпраграма Fact змяняе параметр-пераменную. Па прычыне гэтага пабочнага эфекту ад перамены месц складаемых змяніўся вынік. Тут трэба замест параметра-пераменнай (VAR) паставіць параметр-значэнне.
Многія сучасныя мовы праграміравання змяшчаюць прамыя забароны на падобныя дзеянні.
Прыклад 2.
PROGRAM SideEffect_2;
VAR a, d, z : Integer;
FUNCTION Change(x : Integer) : Integer;
BEGIN
z := z - x; {змяненне глабальнай пераменнай}
Change := Sqr(x); {аргумент у квадрат}
END;
BEGIN
z := 10; a := Change(z); Writeln(a, z); {100, 0}
z := 10; d := 10; a := Change(d) * Change(z);
Writeln(a, z);
z := 10; d := 10; a := Change(z) * Change(d);
Writeln(a, z);
END;
Выканаем праграму на камп’ютары і параўнаем адказы. Відаць, што яны розныя.
Заўвага 1. Трэба пазбягаць залежнасці падпраграм ад глабальных у адносінах да яе пераменных.
Заўвага 2. Параметр-масіў лепш апісваць як параметр-пераменную (VAR) ці як параметр-канстанту (CONST), каб кампілятар не будаваў копію масіву як лакальную пераменную і не перасылаў туды значэнні. Такім чынам мы эканомім і памяць, і час выканання праграмы. Гэта адносіцца і да іншых складаных тыпаў даных.
Але для параметраў тыпу FILE ёсць наступнае абмежаванне: такія параметры заўсёды павінны быць параметрамі-пераменнымі (з VAR).
Рэкурсія і ітэрацыі
Для большасці вылічальных задач ітэрацыя – паслядоўнае вылічэнне – аказваецца эфектыўней, чым рэкурсія, але для многіх задач, якія працуюць з данымі складанай структуры, выкарыстанне рэкурсіі з’яўляецца пераважным.
У целе падпраграмы вядомы (даступны) усе аб’екты, якія апісаны ў ахопліваючым блоку, у тым ліку і імя самой падпраграмы. Такім чынам, унутры цела падпраграмы магчымы выклік самой падпраграмы.
Працэдуры і функцыі, якія выкарыстоўваюць выклікі «саміх сябе», называюцца рэкурсіўнымі.
Дапушчальна таксама ўскосная рэкурсія, пры якой, напрыклад, падпраграма A выклікае падпраграму B, якая ў сваю чаргу выклікае падпраграму C, а апошняя – першапачатковую падпраграму A.
Добра вядома, што існуе шмат рэкурсіўных матэматычных алгарытмаў, напрыклад вылічэнне n!:
n! = (n – 1)! * n, 0! = 1, 1! = 1.
FUNCTION Fact(N : Byte): Longint;
BEGIN
IF N = 0 THEN Fact := 1 ELSE Fact := N * Fact(N - 1);
END;
Выкананне рэкурсіўнай праграмы адбываецца ў два этапы.
На першым этапе здзяйсняецца пабудова рэкурсіўных суадносін і частковае вылічэнне з затрымкай выканання дзеянняў, якія не могуць быць выкананы на дадзеным этапе.
Затрымка вылічэнняў абумоўлена тым, што ў апісанні рэкурсіўнай падпраграмы заўсёды прысутнічае зварот да той самай падпраграмы.
Першы этап завяршаецца пасля выканання так званай умовы завяршэння рэкурсіі. (Гэта дно рэкурсіі.)
На другім этапе здзяйсняюцца вылічэнні дзеянняў на аснове рэкурсіўных суадносін.
У мове Pascal няма ніякіх абмежаванняў на рэкурсіўныя выклікі падпраграм, неабходна толькі добра разумець, што кожны чарговы рэкурсіўны выклік прыводзіць да ўтварэння новай копіі лакальных аб’ектаў падпраграмы, і ўсе гэтыя копіі, якія адпавядаюць ланцужку актывізаваных і незавершаных рэкурсіўных выклікаў, існуюць незалежна адна ад адной.
Рэкурсіўныя падпраграмы – сродак, зручны для чалавека, але даволі накладны для ЭВМ. Звычайна рэкурсіўныя падпраграмы прымяняюць пры невялікай глыбіні рэкурсіі, калі час ліку і затраты памяці не вельмі вялікія.
Праграміруючы рэкурсію, заўсёды трэба памятаць аб умове яе заканчэння, бо ў адваротным выпадку падпраграма будзе бясконца звяртацца сама да сябе і тэарэтычна ніколі не спыніцца, але хутчэй за ўсё праграма вычарпае рэсурсы ПК, паколькі кожны зварот да падпраграмы патрабуе чарговай порцыі аператыўнай памяці.
Трэба ўмець адрозніваць, дзе рэкурсія, а дзе ітэрацыя.
Наступныя алгарытмы прыстасуем да рэкурсіўных.
Задача 1. Падлічыць N-ы лік Фібаначы: f0 = 1, f1 = 1, fn = fn–1 + fn–2, n 2.
FUNCTION ChFR(n : Integer) : Integer;
BEGIN
IF (n = 0) OR (n = 1) THEN ChFR := 1
ELSE ChFR := ChFR(n - 2) + ChFR(n - 1)
END;
Задача 2. Знайсці НАД(a, b) (НАД – найбольшы агульны дзельнік).
FUNCTION HAD(a,b : Integer) : Integer;
BEGIN
IF b = 0 THEN HAD := a ELSE HAD := HAD(b, a MOD b)
END;
Задача 3. Падлічыць значэнне сумы элементаў
CONST k=50;
TYPE AR = ARRAY[1..k] OF Real;
VAR a : AR;
s : Real;
n, і : Integer;
FUNCTION Sum(VAR a : AR; n : Integer) : Real;
BEGIN
IF n = 1 THEN Sum := a[1]
ELSE Sum := Sum(a, n - 1) + a[n]
END;
BEGIN
n := 10;
FOR і := 1 TO n DO a[і] := Random * 100 - 50;
S := Sum(a, n);
Write('сума=', S);
END.
Задача 4. Знайсці найбольшае значэнне сярод лікаў .
Алгарытм. Зводзім пошук да Max{a, b}. Маем:
Max{a1, …, an}=Max{Max{a1, …, an-1}, an}, Max{a1}=a1
CONST n=15;
TYPE
Vect=ARRAY[1..n] OF Real;
VAR
i : Integer;
a : Vect;
FUNCTION Maximum(VAR a : Vect; n : Integer) : Real;
VAR M : Real;
BEGIN
IF n=1 THEN Maximum:=a[1]
ELSE
BEGIN
M:=Maximum(a, n-1);
IF M<=a[n] THEN Maximum:=a[n]
ELSE Maximum:=M
END;
END;
BEGIN
FOR i := 1 TO n DO Read(a[i]);
Writeln;
Writeln(Maximum(a, n):9);
Readln
END.