Рекурсиялар

Көмекші бағдарламалардың денесіндегі операторлардың орындалу барысында өзін-өзі шақыру процесі рекурсия деп аталады. Рекурсивті бағдарламаларда көмекші бағдарламаның орындалуы есептеу параметрінің белгілі бір мәнінен бастап тізбектей төменгі деңгейлі мәніне қарай қашан есептің тривиальды нәтижесі алынғанға дейін жүреді. Функцияның әр рекурсивті орындалуында оның алдыңғы айнымалылары бағдарламалық ағым деп аталатын жадта сақталады. Рекурсивті функциялар құрғанда бағдарламалық ағымның шексіз емес екендігін есте ұстаған жөн (егер ағым толып кетсе, бағдарламаның орындалуы үзіліп кетеді). Рекурсияның мысалы ретінде төмендегі N санының факториалын табатын функцияны келтіруге болады:

N санынын Факториалын табу үшін рекурсия кұру мысалы:

PROGRAM Recurs;

VAR N:lnteger; F:Longint;

FUNCTION Fact(N:lnteger):Longint;

Begin

lfN<0 Then Begin Writeln(N-ді дұрыс енгізіңіз');

Fact:=0 End Else іf N=1 Then

Fact:=1 Else Fact:=N*Fact(N-1);

End;

BEGIN Readln(N);

F:=Fact(N); Writeln('FN=',F);

Readln END.

Бұл бағдарламаның орындалу барысында негізгі бағдарламадан Fact функциясы шақырылады. Функцияның денесі N санын 0-мен салыстырудан басталады. Егер сан теріс немесе 0-ге тең болса, онда функция 0-ді меншіктейді де орындалуын тоқтатады. Егер сан 1 -ге тең болса функцияның мәні 1 -ді меншіктейді де орындалуын тоқтатады. Егер санның мәні 1-ден артық болса, онда басқару Fact:=N*Fact(N-1) операторына барады да N-нің мәні 1-ге дейін жеткенше функцияның орындалуы қайталанады(факториалдың тривиальді мәні 1-ге тең болғандықтан N=1). Функция рекурсивті процес тоқтағаннан кейінгі көбейтінді нәтижесін меншіктейді де орындалуын тоқтатады. Мысалы N=5 болғанда Fact функциясы төмендегідей орындалады:

N=5; 5>1; Fact=5*Fact(4);

N=4; 4>1; Fact(4):=4*Fact(3);

N=3; 3>1; Fact(3):=3*Fact(2);

N=2; 2>1; Fact(2):=2*Fact(1);

N=1; 1=1; Fact(1):=1;