Toshkent axborot texnologiyalari universiteti urganch filiali kompyuter injiniringi fakult

Murakkab rekursiya
Biroz murakkabroq sxema bo'lishi mumkin: A funktsiyasi B funktsiyasini chaqiradi, bu esa o'z navbatida A ni chaqiradi. Bu murakkab rekursiya deb ataladi. Ma'lum bo'lishicha, birinchi bo'lib tasvirlangan protsedura hali tasvirlanmaganini chaqirishi kerak. Buning mumkin bo'lishi uchun oldinga tavsif talab qilinadi.
procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры}
procedure B(n: integer); {Опережающее описание второй процедуры}
procedure A(n: integer); {Полное описание процедуры A}
begin
writeln(n);
B(n-1);
end;
procedure B(n: integer); {Полное описание процедуры B}
begin
writeln(n);
if n<10 then
A(n+2);
end;

B protsedurasining oldinga e'lon qilinishi uni A protsedurasidan chaqirish imkonini beradi. A protsedurasining oldinga e'lon qilinishi bu misolda talab qilinmaydi va estetik sabablarga ko'ra qo'shilgan.

Rekursiya bilan siklni simulyatsiya qilish
Agar protsedura o'zini o'zi chaqirsa, unda, aslida, bu uning tarkibidagi ko'rsatmalarning takroriy bajarilishiga olib keladi, bu tsiklning ishlashiga o'xshaydi. Ba'zi dasturlash tillarida aylanma konstruktsiyalar umuman mavjud emas, bu esa dasturchilarni rekursiyadan foydalangan holda takrorlashni tashkil qilishni qoldiradi (masalan, Prolog, bu erda rekursiya asosiy dasturlash texnikasi).

Masalan, for siklining ishini simulyatsiya qilaylik. Buning uchun bizga, masalan, protsedura parametri sifatida amalga oshirilishi mumkin bo'lgan qadam hisoblagichi o'zgaruvchisi kerak.

procedure LoopImitation(i, n: integer);
{Первый параметр – счетчик шагов, второй параметр – общее количество шагов}
begin
writeln('Hello N ', i); //Здесь любые инструкции, которые будут повторятся
if iLoopImitation(i+1, n); //значению n, повторяем инструкции путем вызова
//нового экземпляра процедуры
end;

LoopImitation(1, 10) kabi qo'ng'iroq natijasi hisoblagichni 1 dan 10 gacha o'zgartirish bilan ko'rsatmalarning o'n marta bajarilishi bo'ladi. Bunday holda, u chop etiladi:

Hello N 1
Hello N 2
…
Hello N 10
Umuman olganda, protsedura parametrlari hisoblagich qiymatlarining o'zgarishi chegaralari ekanligini ko'rish qiyin emas.
Quyidagi misolda bo'lgani kabi takrorlanadigan qo'ng'iroq va ko'rsatmalarni almashtirishingiz mumkin.
procedure LoopImitation2(i, n: integer);
begin
if iLoopImitation2(i+1, n);
writeln('Hello N ', i);
end;

Bunday holda, ko'rsatmalar bajarilishidan oldin protsedura rekursiv chaqiriladi. Protseduraning yangi nusxasi, shuningdek, birinchi navbatda, hisoblagichning maksimal qiymatiga erishgunimizcha, boshqa misolni chaqiradi va hokazo. Shundan keyingina oxirgi chaqirilgan protseduralar o'z ko'rsatmalarini bajaradi, so'ngra oxirgisi o'z ko'rsatmalarini bajaradi va hokazo. LoopImitation2(1, 10) ni chaqirish natijasi salomlashishni teskari tartibda chop etishdir:

Hello N 10
…
Hello N 1
Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, u holda 1-misolda biz undan oldingi protseduralardan keyingilariga o'tamiz. 2-misolda, aksincha, keyinroqdan oldingiga.
Nihoyat, rekursiv qo'ng'iroqni ikkita ko'rsatmalar bloki orasiga qo'yish mumkin. Masalan:
procedure LoopImitation3(i, n: integer);
begin
writeln('Hello N ', i); {Здесь может располагаться первый блок инструкций}
if iLoopImitation3(i+1, n);
writeln('Hello N ', i); {Здесь может располагаться второй блок инструкций}
end;

Bu yerda, birinchi navbatda, birinchi blokdagi ko'rsatmalar ketma-ket bajariladi, keyin ikkinchi blokning ko'rsatmalari teskari tartibda bajariladi. LoopImitation3(1, 10) ga qo'ng'iroq qilganda biz quyidagilarni olamiz:

Hello N 1
…
Hello N 10
Hello N 10
…
Hello N 1