1

Mavzu: Rekursiya

Bu yerda rekursiya haqida nazariy ma'lumot beriladi. Xohlovchilar yozishi mumkin. Rekursiv ishlanadigan masalalarga ssilkalarni ham qo'yish mumkin.

Rekursiya ga javob

Rekursiya (mendagi ma`lumotga ko`ra) o`zini o`zi chaqiruvchi dastur (asosan qisam dastur)

tushuniladi.
Masalan quyidagi dastur Fibonachchi sonlarning n ta hadini ekranga chiqaradi.
Har safar qism dasturda murojat qilganda qism dastur shu hadni topish uchun rekursiya qiladi
ya`ni o`zini o`zi qayta chaqiradi (o`ziga n-1 va n-2 qiymatlarini berib ishlaydi)

Uses Crt;
Function Fib(n:Integer):Longint;
Var
   i: Longint;
Begin
    If (n=0)or(n=1) then Begin fib:=1;Exit;End else
       fib:=fib(n-1)+Fib(n-2);
End;
Var
   n,i: Longint;
   x: Array [1..100] of Longint;
Begin
     Write('n ni kiriting:');Readln(n);
 For i:=1 to n do
     x[i]:=fib(i)mod 1000000000;
 For i:=1 to n do
     Writeln(x[i]);
End.

Rekursiya ga javob

Lekin katta sonlarda Limit olishi aniq

Rekursiya ga javob

                                     Rekursiya 


Dasturlashda o'z-o'zini chaqiruvchi funksiyaga rekursiv funksiya deyiladi. Bunday chaqiruvga esa rekursiya deyiladi. Matematikada ham ba'zi funksiyalar rekursiv berilishi mumkin.

Dasturda biror funksiyani rekursiv chaqirish uchun, shu funksiyani uning ichida chaqirish kerak bo'ladi:

void rec(int n){
     rec(n - 1);
}

Bu yerda funksiyamizda n parametr bor va u o'z-o'zini  n - 1 parametr bilan chaqiradi. Bu qanday bo'ladi:

Sistema har bir dastur uchun stack-xotira ajratadi. Har bir rekursiv funksiya stekka joylanib boriladi, keyin shu funksiyadan chiqilganda, stek orqali orqaga qaytiladi. Ya'ni eng oxirgisidan chiqiladi, keyin undan bitta oldingisidan va hk.

Ha, rekursiv funksiya o'z-o'zini chaqirishni qachondir to'xtashi kerak, aks holda cheksiz marta chaqirib, xotira yetmay qoladi va StackOverflow xatoligi ro'y beradi. Demak, yuqoridagiga o'xshab rekursiv funksiya tuzib bo'lmas ekan.

Shuning uchun, doim rekursiv funksiya ishlatilganda uni to'xtash shartlari ham bo'lishi kerak. Masalan biror parametrning qiymati 0 dan katta bo'lsa chaqirsin, aks holda chaqirmasin. Albatta bu parametrimiz qachondir 0 dan <= bo'lishi kerak, aks holda bunday shart befoyda bo'ladi:


void rec(int n){

   if (n > 0) rec(n - 1);

}

Agar bu funksiyamizni asosiy qismda rec(4) deb chaqiradigan bo'lsak, funksiya n ni tekshiradi, agar u 0 dan katta bo'lsa u o'z-o'zini  rec(4 - 1) qilib chaqiradi. rec(4 - 1) o'z navbatida shu funksiyani rec(3 - 1)  qilib chaqiradi. rec(3-1)  rec(2-1) ni chaqiradi. rec(2 - 1) esa rec(1-1) ni chaqiradi. rec(1-1)  esa hech qanday funksiyani chaqirmaydi, chunki n == 0. Shu yerda rec(1-1) dan chiqiladi va boshqarish, rec(1-1) ni chaqirgan rec(2-1) ga o'tadi. (Bitta yuqori pog'ona). rec(2 - 1) o'z navbatida if dan keyinga o'tadi va u ham tugaydi. Boshqarish rec(3 - 1) ga o'tiladi. Undan rec(4 - 1)ga va undan asosiy dasturga qaytiladi. Shunday qilib rekursiyamiz to'xtaydi.


http://acm.tuit.uz/forum/img/m/3/t/p16v2kd4031qo197grbe2pvm71.png


Hozircha funksiyamiz faqat o'zini chaqiryapti. Unga boshqa amallarni ham qo'shish kerak, aks holda bunday funksiyadan foyda yo'q. Keling, har safar n ni ekranga chiqaraylik:

void rec(int n){

   System.out.println(n);

   if (n > 0) rec(n - 1);

}

Dastur bajarilishi natijasida, ekranga quyidagi sonlar chiqadi:

4
3
2
1
0

Ya'ni, har safar funksiyamiz o'z-o'zini chaqirishidan oldin parametrni ekranga chiqarib keyin n ni tekshirib, agar n>0 bo'lsa n - 1 parametr bilan o'zini chaqiradi. Aytish kerakki, ixtiyoriy ichki funksiya ishini tugatganda, uni oldingi funksiyaning qayerida chaqirilgan bo'lsa, boshqarish o'sha joyga o'tadi va o'shayerdan dastur davom etib ketadi.

Kodimizni sal o'zgartiraylik, ekranga chiqarishni if dan keyinga qo'yamiz:

void rec(int n){

   if (n > 0) rec(n - 1);

   System.out.println(n);

}

Natija qanday o'zgaradi? Ekranga chiqarish qachon bo'ladi? qachonki ifdan keyinga o'tilsa, ifdan keyinga qachon o'tiladi? qachonki, n <= 0 bo'lsa va funksiya o'z-o'zini boshqa chaqirmasa. Demak, rec(4)  chaqirilsa, birinchi bo'lib if dan keyingi o'tadigan ichki funksiyamiz bu oxirgisi rec(1-1). Demak, birinchi bo'lib ekranga 0 chiqadi. Undan so'ng rec(2-1) dan chiqiladi. Chiqishdan oldin ekranga 2-1 ya'ni 1 chiqariladi va hk. Demak, sonlar teskarisiga chiqarkan (birinchi dasturdagiga nisbatan)

Demak, natija quyidagicha o'zgaradi:


0
1
2
3
4

Endi faktorialni hisoblaydigan rekursiv funksiya tuzamiz:


0! = 1;

n! = (n - 1)! * n

yoki

n! = n * (n - 1)!


int fact(int n){
    if (n == 0) {
        return 1; 
    } else {
      return n * fact(n - 1);
    }
}

Rekursiyani chekliligi:

n==0 shart bajarilganda rekursiv chaqiruv bo'lmaydi, n > 0 da esa funksiya n - 1 parametr bilan o'zini chaqiradi. Demak, parametr qachondir (n ta qadamda) 0 ga tenglashadi va rekursiya tugaydi.

To'g'ri ishlashi:

Rekursiya oxirgi n = 0 parametrli funksiyadan qaytganda 1 javob qaytaradi. 0 parametrli funksiyani esa n = 1 parametrlisi chaqirgan. Chaqirilgandan so'ng hech qanday operatsiya yo'q va u ham 1*1 qaytarib chiqadi, ya'ni 1 * fact(0). 1 parametrlisini 2 chaqirgan. U ham 2*1*1 qaytarib chiqadi, 2*fact(1). Uni 3 chaqirgan va hk.

Natijada N parametrli funksiyamizga (boshlang'ich funksiyamiz) kelgunga n*(n-1)*(n-2)*...*3*2*1*1  hisoblanadi.


Rekursiv dasturlar o'zining qisqaligi va ko'pgina qiyin masalalarni rekursiv yo'lda oddiygina yechish mumkinligi bilan ajralib turadi. Shuni ham unutmaslik kerakki, rekursiv funksiyaning har bir kopiyasi chaqirilganda sistema stekida undagi va barcha undan oldingi funksiyalarning parametrlari saqlanib turadi. Bu esa xotira bilan hisob-kitob qilishga olib keladi. Ayniqsa perebor masalalarida rekursiv dasturning chuqurligi C^N, ya'ni darajali funksiya tarzida ortib ketishi mumkin. Bunday hollarda, rekursiyadan chiqish shartlarini yaxshilab tahlil qilib, iloji boricha funksiyalarning ortiqcha chaqirilmasligini ta'minlash kerak.

Buning yo'llaridan biri - bu hisoblangan qiymatlarni qayta hisoblamaslikdir. Bu uchun har bir parametrdagi qiymatlarni massivda saqlab ketamiz, agar yana shu qiymatlarni hisoblash kerak bo'lganda rekursiv chaqirmasdan, massivdan tayyor qiymatni olamiz. Bu usul memorizatsiyali rekursiya deyiladi.

Bunga misol tariqasida Fibonachchi sonlarini hosiblashning rekursiv funksiyasini qaraylik.

Fibonachchi sonlarida:


F(0) = 0
F(1) = 1
F(n) = F(n - 2) + F(n - 1)



int fib(int n){
  if (n == 0){
     return 0;
  } else {
      if (n == 1) return 1; else return fib(n - 2) + fib(n - 1);
  }
}

Faraz qilaylik, asosiy dasturda fib(5) chaqirildi.

N == 0 ham N == 1 ham emas. Funksiya birinchi turgan fib(n-2) ni chaqiradi. Ya'ni 5 - 2 = 3.

U ham 0 yoki 1 emas, bu yoqda ham fib(n-2) chaqiriladi. Ya'ni 3-2 = 1. Endi n==1 funksiyamiz 1 qiymat qaytaradi va bitta oldingi funksiyaga qaytadi, fib(3) ga. Unda hali fib(n - 1) bor. Ya'ni 3-1=2 uchun yana chaqiriladi. U ham birinchi turgan fib(n-2) ni chaqiradi, 2-2=0 ni. 0 da 0 qaytadi. demak fib(2) da:

return 0 + fib(2-1)  qoldi.

fib(2-1) ham chaqirilib, undan 1 qaytgandan so'ng, fib(2)  0 + 1  javob qaytaradi. Endi fib(3) ga qaytamiz. Unda fib(1) hisoblangan fib(2) ham bo'ldi. U ham 1 + 1 qaytaradi. Demak, endigina fib(5) ning   return  fib(3) + fib(4)  qismiga keldik. Bu yoqda fib(3) dan chiqildi. Endi fib(4) ga kirish kerak. smile

fib(4) da fib(2) + fib(3).  Birinchi fib(2)  chaqiriladi. E'tibor bering, fib(2) ni bir marta hisobladik, lekin rekursiya yana qayta hisoblaydi. Undan keyin fib(3) chaqiriladi. U ham qayta hisoblanadi. keyin fib(4) natija qaytaradi va nihoyat, fib(5) imizda natija chiqadi.



Rekursiya fib(2)  va fib(3) larni ikki marta hisobladi. Yana har biri uchun necha marta rekursiv chaqiruv bo'ladi. Faraz qiling n = 100 bo'lganda nima bo'lardi.

Shu uchun, agar biz  fib(2)  va fib(3)  ni qiymatini massivda saqlab qo'yganimizda O(1) da javobni olardik, ya'ni massivga 1 ta murojaatda. Nafaqat 2 va 3 uchun, barcha hisoblangan qiymatlarni saqlab boramiz. Shunday qilib, rekursiyani qisqartiramiz:

public class Fibonachchi{

    static int MAXN = 50;   // N ning eng maksimal qiymati
    static int[] a = new int[MAXN]; 
    static boolean[]  yes = new boolean[MAXN]; 

    static int fib(int n){
      if (yes[n]){
         return a[n];
      } else {
          a[n] = fib(n - 2) + fib(n - 1);
          yes[n] = true;
          return a[n];
      }
    }

    public static void main(String[] args){
     
       yes[0] = true;  a[0] = 0;
       yes[1] = true;  a[1] = 1;
     
       // Fibonachchi sonlarining birinchi 46 ta elementi:

       for (int i = 0; i < 46; i++)
           System.out.println(i+" "+fib(i));

    }

}

Ana endi bitta qiymat ikki marta hisoblanmaydi. Chunki, hisoblangan qiymatlarni a massivda saqlab kettik. Yana bir boolean[] yes massiv ochib, fib(N) hisoblangan bo'lsa yes[N]ni true qilib kettik va yes[N]ga qarab, kerak bo'lgandagina rekursiv chaqiruv qildik.

Boshida yes[0]= true, yes[1]= true. Funksiya ishlashi davomida qolganlari ham true bo'lib boradi. Aytish kerakki, faqat yes[N]= false bo'lganlari uchungina rekursiyamiz chaqirilgani uchun, rekursiya chuqurligi (o'z-o'zini chaqirishlari soni) ko'pi bilan MAXN ta bo'lishi mumkin.



Endi rekursiya bilib olingandan so'ng, ancha narsa tushunarli bo'lgan bo'lsa kerak. QuickSort dagi ikki marta rekursiv chaqiruv va hk. Hali ko'p metodlarda rekursiya ishlatiladi, shu uchun yaxshilab tushunib olish kerak.

Hozircha shu, yana kimda qanaqa fikrlar yoki savollar bo'lsa, marhamat...

Xatolar uchun oldindan uzr...

Rekursiya ga javob

Quyidagi masalalarni rekursiv usulda ishlab ko'ring:

M004. Ньютон Биноми

Nyuton binomi uchun:


K = 0 da F(N,K) = 1
va
N > 0   da   F(N,K) = F(N - 1,K - 1) + F(N - 1, K)   aks holda   F(N, K) = 0


Birinchi oddiy rekursiyada, so'ng memorizatsiyali rekursiyada ishlab ko'ring. Oddiy rekursiya Time Limit olishi kerak.

Uzr bu masala dlinnaya arifmetikaga ekan. Baribir xohlaganlar ishlab ko'rishi mumkin. Javada BigIntegerni ishlatish mumkin.

6 (edited by davr_2838 2012-07-22 10:13:51)

Rekursiya ga javob

Rekursiv funksiyalar 2 xil bo`ladi oddiy va vositali siz aytgan ma`lumotlar oddiy rekursiv funksiyalar, vositalisi haqida ham ma`lumot bersangiz.

Rekursiya ga javob

Ma'lumotlar uchun rahmat! Davom ettirsez yaxshi bo'lardi. oldindan rahmat

Rekursiya ga javob

Katta rahmat shu kabi ma`lumotlarni ko`proq berib tursangiz xammamizga yaxshi bo`lardi. smile

Rekursiya ga javob

M004 masalasini yechib kordim rekursiv procedura ni foidalangan holda pascalda. Lekin n = 100  bolganda sonlar xato boliyapti qanday  maslahat berasiz?

Rekursiya ga javob

n = 100 uchun sonlar chegaraga sig'maydi. Siz uzun sonlar bilan ishlashingizga to'gri keladi.