Рекурсия және оның сипатталуы

Рекурсия – бұ л қ осалқ ы программаның қ ұ рамындағ ы операторлардың орындалуы барысында ө зін-ө зі шақ ыратын, есептеу процесін ұ йымдастыру тә сілі.

Енді факториалды есептеу мысалын қ арастырайық. Программа edinput компонентінен N бү тін санын алып, LBOutput компонентіне Factorial рекурсивті функциясының кө мегімен N! -дің мә нін шығ арады.

Дұ рыс ұ йымдастырылғ ан рекурсивті қ осалқ ы программ орындалғ анда алгоритмнің қ андай да бір ағ ымдағ ы дең гейдегі ұ йымдастырылуынан тө менгі дең гейге кө шу бірнеше рет жү зеге асады, ол қ ойылғ ан есептің тривиалды, шешімін алғ анша тізбекті тү рде жалғ аса береді. Біздің жағ дайда тривиалды шешім N=0 болғ ан жағ дайда алынады да, рекурсия тоқ тайды.

Procedure TfmExample, bbRunClick(Sender: TObject);

Function Factorial (N: Word): Extended;

Begin

If N=0 then

Result: =N*Factorial(N-1)

End;

Var

N: integer;

Begin

Try

N: =StrToInt(Trim(Edinput.Text));

Except

Exit

End;

LBOutput.Caption: =FloatToStr(Factorial(N))

End;

Алгоритмді рекурсивті тү рде ұ йымдастыруда программа мә тіні ө те ың ғ айлы, шағ ын, бірақ, орындалуы баяу жә не стектің толық орындалуы мү мкін (қ осалқ ы программа ә рбір шақ ырылғ ан сайын оның локальды парамерлері ерекше ұ йымдастырылғ ан «программалық стек» деп аталатын жады бө лігіне орналасады).

Рекурсивті шақ ыру жанама болуы мү мкін. Мұ ндай жағ дайда қ осалқ ы программа ө зіне бірінші қ осалқ ы программаны шақ ыру жазылғ ан басқ а қ осалқ ы программаны шақ ыру арқ ылы оралады.

Мысалы:

Procedure A (i: Byte);

Begin

…

B(i);

…

Procedure B (j: Byte);

Begin

…

A (i);

…

Егер «ә рбір пайдаланылатын идентификатор алдын-ала сипатталуы тиіс» деген ережеге сү йенсек, онда мұ ндай программалық қ ұ рылымды пайдалануғ а болмайды. Ал, мұ ндай сипаттау болып жатса, онда алдын-ала бейнелеу енгізіледі.

Procedure B (j: Byte); Forward;

Procedure A (i: Byte);

Begin

…

B(i);

…

End;

Procedure B;

Begin

…

A(j);

…

End;

Келтірілген мысалдан кө ріп отырғ анымыздай, алдын-ала бейнелеуде, процедураның тақ ырыбы хабарланып, ал оның денесі стандартты П директивасымен алмасады. Сондай-ақ, процедура денесі тақ ырыбымен жазылады, бірақ бұ рын сипатталғ ан формальды параметрлер кө рсетілмейді.

ТАПСЫРМА:

Object Pascal тілінде нақ ты санды кез келген дә режеге шығ ару операциясы қ арастырылмағ ан. Дегенмен, бұ л есепті Exp жә не ln математикалық стандартты функцияларын пайдалана отырып шығ аруғ а болады:

ТАПСЫРМАНЫ ОРЫНДАУҒ А Ә ДІСТЕМЕЛІК НҰ СҚ АУЛАР:

А жә не В екі нақ ты параметрлері бар, А-ны В-ғ а дә режелегендегі нә тижені беретін Power деген атпен функция қ ұ райық.

Біздің қ ұ рғ ан fmExample оқ у формасында bbRunClick оқ иғ асын ө ң деуші edInput компонентінің мә тінді оқ ып, ең болмағ анда бір бос орынмен бө лінген екі санды бө ліп (ерекшелеп) кө рсетуге тырысады. Егер осыны орындау мү мкін болса, онда ол Power функциясына екі рет оралады: алдымен бірінші x саны, екінші y санына дә реже болады; одан кейін x санына y саны дә реже болады.

Procedure TfmExample. bbRunClick(Sender: TObject);

Function Power(A, B: real): real;

{Функция А санын В санына дә режелейді. ө йткені теріс саннан логарифм алынбайды, А-ның мә нін тексеру жү зеге асырылады: теріс мә н оң мә нге алмастырылады. Сонымен қ атар, кез келген санның ноль дә режесі бірге тең }

Begin

If A> 0 then

Result: =Exp(B*Ln(A))

Else if A< 0 then

Result: =Exp(B*Ln(Abs(A)))

Else if B=0 then

Result: =0;

End; //Power

Var

S: string; x, y: real;

Begin

{edInput компонентінен жолды оқ ып, одан кем дегенде бір бос орынмен бө лінген екі нақ ты санды бө ліп аламыз}

s: =edInput.Text

if (S=’’) or (pos(‘’, S)=0) then

Exit; //Мә тін немесе бос орын болмаса, онда ары қ арай жұ мыс орындалмай тоқ татылады

Try //Бірінші санды бө ліп аламыз:

x: =StrToFloat(copy(s, 1, pos(‘’, s)-1)); //Егер бос орынғ а дейінгі символдарды ө шірсек, онда екінші санды бө ліп аламыз.

delete(s, 1, pos(‘’, s));

y: StrToFloat(trim(s));

except

Exit; //Қ ате пайда болғ ан жағ дайда жұ мыс тоқ татылады.

End;

MmOutput.Lines.Add(FloatToStr(Power(x, -y)));

MmOutput.Lines.Add(FloatToStr(Power(x, -y)));

end;

Бұ л жерде біз Power функциясын шақ ыруда нақ ты санды FloatToStr жолына тү рлендіретін стандартты функцияны шақ ыруда пайдаланатын параметр ретінде кө рсеттік: Power функциясын шақ ыру кезінде х жә не у параметрлері – бұ л шынайы параметрлер. Олар функция тақ ырыбындағ ы а жә не В формальды параметрлерінің орнына қ ойылып, одан кейін тиісті ә рекеттердің орындалуы жү зеге асады. Алынғ ан нә тиже «Result» атты арнайы айнымалығ а меншіктеледі. Программада Power функциясы екі рет шақ ырылады: алдымен х жә не у праметрлерімен, сондық тан екі нә тиже алынады.

Ұ сынылатын ә дебиеттер: [1-9]

Бекіту сұ рақ тары:

1. Object Pascal тіліндегі процедуралар мен функциялардың қ ызметі қ андай жә не олар қ алай сипатталады?

2. Рекурсия дегеніміз не?

3. Жергілікті жә не глобальды атаулар деп қ андай атауларды айтамыз?

4. Процедуралар мен функциялардың орналасуының қ андай ерекшелігі бар?

5. Қ осалқ ы программаларғ а қ олданылатын қ андай стандартты директивалар бар?

6. Формальды параметрлер дегеніміз не?

7. Ескерілмейтін параметрлер деп қ андай параметрлерді айтамыз жә не олар қ алай сипатталады?

8. Массив параметрлер деп қ андай параметрлерді айтамыз жә не олар қ алай сипатталады?

9. Ашық массив дегеніміз не жә не ол қ алай сипатталады?

10. Ашық массивтің жоғ арғ ы шекарасы қ андай стандартты функциямен анық талады?

11. Массив конструкторы дегеніміз не?

12. Вариантты массивтер қ андай жағ дайларда пайдаланылады?

13. GetArrayAverage функциясының қ ызметі қ андай?

14. Процедуралық типтердің негізгі қ ызметі қ андай жә не олар қ алай хабарланады?

15. Object Pascal тілінде қ анша процедуралық тип бар?

16. Рекурсия дегеніміз не жә не ол қ алай ұ йымдастырылады?

17. Нақ ты a, b жә не с сандары берілген. Тө мендегі ө рнектердің мә нін есептейтін программа жазың дар:

18. А) S=(max(a, a+b)+max(a, b+c))/(1+max(a+b*c, a*b+c));

19. В) S=(max(a, b, c)+max(ab, bc, ac))/min(1/a, 1/b, 1/c)-max(a/b, a/c, b/c)).

20. Есептең із:

21. Z-(V₁+V₂+V₃)/3, мұ ндағ ы V₁, V₂, V₃ – радиустардың ө лшемі сә йкес r₁, r₂, r₃ – болып келген шар кө лемдері.

22. Нақ ты X₁, Y₁, X₂, Y₂…X₁₀, Y₁₀ сандар берілген. Тө белерінің сә йкес координаталары (X₁, Y₁), (X₂, Y₂)…(X₁₀, Y10) болатын онбұ рыштың периметрлерін табың дар.

23. М жә не n натурал сандары a₁, …, a_n, b₁, …, b_m, c₁…, c₃₀ бү тін сандары берілген. Табың ыз:

24. Динамикалық жады дегеніміз не?

25. Кө рсеткіш дегеніміз не жә не не ү шін пайдаланылады?

26. Типтелмеген кө рсеткіштердің қ ызметі қ андай?