Заголовок

Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Urganch filiali 914-22 guruh talabasi Ozodov Behzodbekning ma’lumotlar tuzilmasi va algoritmi fanidan tayyorlagan taqdimoti

Mavzu: Rekursiv funktsiyalar va algoritmlar.

Rekursiv funktsiyalar va algoritmlar.

• Funksiya o’ziga o’zi to’g’ridan-to’g’ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi. Rekursiv algoritmdan foydalanib, ba'zi muammolarni juda oson hal qilish mumkin.

Matematik talqini

• Dasturchi birinchi n natural sonlarning yig'indisini aniqlashi kerak bo'lgan muammoni ko'rib chiqaylik, buning bir necha yo'li bor, lekin eng oddiy yondashuv 1 dan n gacha bo'lgan sonlarni qo'shishdir.
• Shunday qilib, funksiya shunchaki shunday ko'rinadi: f(n)=1+2+3+…….+n
• Lekin buni ifodalashning boshqa matematik yondashuvi bor
• F(n)=1 n=1 f(n)=n+f(n-1) n>1

• Yondashuv (#1) va yondashuv (#2) o'rtasida oddiy farq bor va bu (2) yondashuvda "f ()" funksiyasining o'zi funksiya ichida chaqiriladi, shuning uchun bu hodisa rekursiya va o'z ichiga olgan funksiya deb nomlanadi. Rekursiya rekursiv funksiya deb ataladi, natijada bu dasturchilar qo'lida ba'zi muammolarni ancha oson va samarali kodlash uchun ajoyib vosita.

Rekursiyada asosiy shart nima?

Rekursiv dasturda asosiy holatning yechimi taqdim etiladi va katta masalaning yechimi kichikroq masalalar bilan ifodalanadi.

int fact(int n)

{

if (n < = 1) // asosiy holat

return 1;

else

return n*fact(n-1);

}

Yuqoridagi misolda, n <= 1 uchun asosiy holat aniqlangan va sonning kattaroq qiymatini kichik songa aylantirish orqali hal qilish mumkin.

Rekursiyani to’g’ri tashkil qilish shartlari

Har qanday to’g’ri tuzilgan rekursiya asosini ikkita shart tashkil qiladi.

Rekursiya asos sharti

Funksiyaning o’ziga o’zgartirilgan argument bilan murojaat qilish sharti.

Rekursiv funksiya qaysidir vaqtga kelib o’ziga murojaat qilishni to’xtatishi kerak bo’ladi. Aynan shu narsani rekursiya asos sharti ta’minlab beradi

Nima uchun rekursiya kerak Aslini olganda, har qanday rekursiv ishlangan masalani iterativ usulda ishlash mumkin va buning aksi ham to’g’ri.Buning ustiga rekursiv yechim har doim xotiradan qo’shimcha joy talab qiladi. Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning yetarlicha sabablari bor:

Rekursiya deyarli hamma joyda ishlatiladi. Ba’zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba’zi masalalarning iterativ yechimi juda ham uzun bo’lib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo’lmaydi. 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. Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. shunday dasturlash tillari borki ularda umuman takrorlanish operatorlari yo’q va bu borada butunlay rekursiyaga tayanadi. Haskell va Erlang shular jumlasidan.

Rekursiv triada Parametrizatsiya qilish – masala shartini tasniflash va uni xal etish uchun parametrlar aniqlanadi (masala kolamidan kelib chiqib ya’ni har safar masala kolami kamayishi kerak ); Rekursiya bazasi(asosi) – masala yechimi aniq bo’lgan trivial (to’xtaydigan ) holat aniqlanadi , ya’ni bu xolatda funksiyani o’ziga murojat qilishi talab etilmaydi Dekompozitsiya (butun qismlarga ajratsih ) umumiy xolatni nisbatan ancha oddiy bo’lgan o’zgargan parametrli qism masalalar orqali ifodalaydi Rekursiv yoki interatsion usul samaradorligi berilgan masalani xal qiluvchi dasturni turli boshlang’ich qiymatlarda taxlil etish orqali aniqlanadi. Rekursiv algoritmlarni samaradorligini oshirish ko’pincha triada bosqichlarini qayta ko’rib chiqish natijasida amalga oshishi mumkun.

Arifmetik progressiyani birinchi hadi va ayirmasi berilgan. N ta hadini aniqlovchi rekursiv funksiya tuzing #include using namespace std; int progressiya(int a, int d, int n) { if (n == 1) { cout<> a; cout << "Ayirmani kiriting: "; cin >> d; cout << " (N) ni kiriting: "; cin >> n; int natija = progressiya(a, d, n); return 0; }

E’TIBORINGIZ UCHUN RAHMAT!