Дәріс 11. Рекурсия. Модульдер.

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

Мысал 1: Натурал N санның факториалын анық тауды қ арасты-райық:

мұ нда, N факториал оның алдындағ ы (N-1) факториал, ал (N-1) факториал(N-2) факториал (N! = N*(N-1)! =N*(N-1)*(N-2)!) т. с.с кө мегімен анық талып тұ р.

Мысал2: Фибоначи сандары бірінші мү шесі F(1)=1, ал екінші мү шесі F(2)=1 деп алынып n- натурал саны ү шін F(n+2)=F(n)+F(n+1) формуласы бойынша есептелінеді. Формулада келесі мү шенің мә ні оның алдың ғ ы мү шелеріне байланысты есептелінетіні анық талғ ан. Берілген формуламен есептегенде шығ атын тізбектің алғ ашқ ы жеті элементі 1, 1, 2, 3, 5, 8, 13 -ке тең болады.

Программада ө зін - ө зі шақ ыратын ішкі программа рекурсивті деп аталады. Негізінен берілген рекурсивтік формула бойынша шығ арылатын есепті рекурсияны қ олданбай шығ аруғ а болады. Бірақ ол жағ дайды программаның сапасы жә не оның алғ ашқ ы формулағ а эквиваленттігі дұ рыс бола ма деген мә селелер туындауы мү мкін. Рекурсивті алгоритмдер программалау тілдерін, операциялық жү йелерді жә не трансляторларды қ ұ растырғ анда ө те жиі қ олданалады.

Мысал 1. N! –ды есептеудің программасын параметрлі қ ай-талау операторының жә не рекурсия ә дісінің кө мегімен қ ұ растыр:

Program Factorial1;

var n, i: integer;

fact: Longint;

Begin

Writeln ('факториал табатын санды енгіз n? ');

Readln (n);

fact: = 1;

For i: = 1 to n do

fact: =fact*i;

Writeln (n, ' факториал =', fact);

Readln;

End.

Енді факториалды есептеуді рекурсия ә дісі арқ ылы орын-дайық. Бұ л жағ дайда алдымен факториалды есептеуді процедура немесе функция ретінде жеке ө рнектеп аламыз. Одан кейін функция немесе процедураны негізгі программаның қ ажетті жерінде шақ ырып орындаймыз.

Program Factorial2;

var n: integer; {n – факториалы есептелінетін сан }

{факториялды есептеу функциясы}

Function Fact (i: integer): longint;

begin

if i = 0 then

Fact: =1

else

Fact: =i*Fact(i-1);

end;

begin

writeln ('факториал табатын санды енгіз n? ');

readln(n);

writeln (n, ' факториал = ', fact(n));

readln;

end.

Мысал2: Бірінші мү шесі F(1)=1, ал екінші мү шесі F(2)=1 деп алынып n- натурал саны ү шін F(n+2)=F(n)+F(n+1) формуласы бойынша есептелінетін Фибоначи сандарын табатын программа қ ұ р.

Program Fibonachi1;

{Фибоначчи сандарын есептеу процедурасы}

Procedure Fibon (n, f1, f2: integer);

begin

if n> 0 then

begin

writeln(f1+f2);

Fibon(n-1, f2, f1+f2);

end;

end;

{негізгі программа}

var n, x, y: integer;

begin

writeln ('Қ андай мү шелерден кейін х, у? ');

readln(х, у);

writeln ('Қ анша мү шесін тапқ ың келеді? n ');

readln (n);

Fibon (n, x, y);

readln;

end.

Есептің шешілуі процедураның кө мегімен ұ йымдастырылғ ан. Процедурағ а негізгі программадан ү ш параметр беріледі. Оның екеуі қ атар тұ рғ ан Фибоначчи сандары, ал ү шіншісі олардан кейін қ атардың қ анша мү шесін анық тауғ а қ ажетті мә лімет. Мысалы: Егер қ атардың алғ ашқ ы сегіз мү шесін тапқ ымыз келсе, онда n=8, х=1, у=0 болуы тиіс.

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