Rekursiv algoritmlar, ularning tahlili. Rekursiyaga doir misollar

Rekursiv algoritmlar, ularning tahlili.Rekursiyaga doir misollar.

REKURSIYA TUSHUNCHASI O’Z O’ZIGA MUROJAT QILISH DEGAN MA’NONI ANGLATADI

Dasturlash nuqtai nazaridan rekursiya – ma’lumotlarni shakllantirish usuli bunda dastur o’z o’zini chaqiradi

Rekursiya bu –obyektni mazkur obyektga murojaat qilish orqali aniqlashdir obyekt, funksiya, algoritm va malumotlar tuzilmasi rekursiv bolishi mumkin

• Rekursiv funksiya bu shu funksiya algoritmini aniqlashda oziga bevosita yoki bilvosita boshqa funksiyalar orqali murojaat qiladi.
• Rekursiyani to'g'ri tashkil qilish shartlari:
• Funksiyaning o'ziga o'zgartirilgan argument bilan murojaat qilish:
• Rekursiv funksiya qaysidir vaqtga kelib o'ziga murojaat qilishni to'xtatishi kerak bo'ladi. Aynan shu narsani rekursiya asos sharti ta'minlab beradi:

Rekursiya deyarli hamma joyda ishlatiladi.

Tree, Graph, Heap, QuickSort, MergeSort, … Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo'lgan Tree va Graphlarda rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib bo'lmaydi, bu esa o'z o'rnida rekursiya qanchalik muhimligini belgilab beradi.

Faktorial iterativ ravishda for operatori yordamida quyidagicha hisoblanishi mumkin:

factorial=1;

for (int counter=n; counter>=1; counter--)

factorial * = counter

Rekursiv va iterativ yondashuvlarning qiyosiy taxlili

1) ikkalasi ham boshqaruvchi strukturaga asoslangan:iterativ – takrorlanuvchi; rekursiya- tanlov ;

2) ikkalasi ham takrorlashni io’z ichiga oladi: iteratsiya-oshkora, rekursiya –funksiyalarni takror chaqirish hisobiga; 3)ikkalasi ham tugallash shartini o’z ichiga oladi

4) ikkalasi ham cheksiz davom etish holatiga tushib qqolishi mumkin;

5) Har qanday rekursiv echish mumkin bo’lgan masalani iterativ echish mumkin;

6) Algoritm va dasturlarni tuzishda rekursiyadan foydalanish vaqtni tejaydi, hajmi kichik bo’ladi, lekin interatsion usulga nisbatan dastur sekinroq ishlaydi hamda ko’proq hotira talab qiladi.

Rekursiv MTga misol: Daraxt tushunchasi:

Daraxt-bu chiziqsiz bog’langan ma’lumotlar.

Daraxt o’zining quyidagi belgilari bilan tasniflanadi:

• Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
• Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojaat qilish mumkin;
• Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni orqaliq yoki terminal (barg) bo’lishi mumkin.

Def.2.

Def.3. Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.

Daraxt bosqichlari soniga daraxt balandligi deyiladi.
0-bosqich
1- bosqich
2- bosqich
3
1
2
Chiqish darajalari.

Daraxtlar klassifikatsiyasi

Eslatma
Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.
1) Agar maksimal darajasi m bo’lsa, u holda bunday daraxt m-tartibli daraxt deyiladi;
2) Agar chiqish darajasi 0 yoki m bo’lsa, u holda to’liq m – tartibli daraxt deyiladi;
3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt binary daraxt deyiladi;
4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binary daraxt deyiladi.
Tugunlar orasidagi bog’liqlikni tavsiflash uchun yana quyidagicha atamadan foydaliniladi: Otao’g’il

Daraxtlarni tavsiflash

Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi
Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.

Mavzuga doir misollar:

Rekursiv funksiyadan foydalanib n sonining faktorialini hisoblash

#include
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n;
std::cout << "n ni kiriting: ";
std::cin >> n;
int result = factorial(n);
std::cout << n << " ning faktoriali: " << result << std::endl;
return 0;
}

Funksiya factorial rekursiv ravishda n sonining faktorialini hisoblaydi. Foydalanuvchidan n ni kiritishi so'rilib, factorial(n) ni hisoblaydi va natijani chiqaradi. Misol uchun, foydalanuvchi n ni 4 kiritgan bo'lsa, natijada 4 ning faktoriali: 24 chiqadi.

E’tiboringiz uchun raxmat!