MohirDox

Ko'rinishi

Rekursiya (Recursion) ​

Rekursiya ​

Rekursiya — funksiyaning o'zini o'zi chaqirish texnikasi.

Bu texnika murakkab masalalarni hal qilish osonroq bo'lgan oddiy masalalarga ajratish imkonini beradi.

Rekursiyani tushunish biroz qiyin bo'lishi mumkin. Uni tushunishning eng yaxshi yo'li — tajriba qilishdir.

Rekursiya misoli ​

Ikki sonni qo'shish oson, lekin sonlar oralig'ini qo'shish murakkabroq.

Quyidagi misolda rekursiya yordamida sonlar oralig'ini ikki sonni qo'shish oddiy amaliga ajratib qo'shamiz:

MISOL

cpp
int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

int main() {
  int result = sum(10);
  cout << result;
  return 0;
}

Tushuntirish ​

sum() funksiyasi chaqirilganda, k parametrini k dan kichik barcha sonlar yig'indisiga qo'shadi va natijani qaytaradi. k 0 ga teng bo'lganda funksiya 0 qaytaradi. Dastur quyidagi bosqichlarni bajaradi:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

ESLATMA

Dasturchi rekursiya bilan ehtiyot bo'lishi kerak — hech qachon to'xtamaydigan yoki haddan tashqari ko'p xotira/protsessor ishlatadigan funksiya yozish juda oson. Ammo to'g'ri yozilganda rekursiya juda samarali va matematik jihatdan nafis yondashuv bo'lishi mumkin.

Teskari sanash ​

Rekursiya bilan teskari sanash funksiyasi:

MISOL

cpp
void countdown(int n) {
  if (n > 0) {
    cout << n << " ";
    countdown(n - 1);
  }
}

int main() {
  countdown(5);
}

Funksiya n - 1 bilan o'zini chaqiradi va n 0 ga teng bo'lganda to'xtaydi.

Faktorial ​

Rekursiv funksiya yordamida 5 ning faktorialini hisoblash:

MISOL

cpp
int factorial(int n) {
  if (n > 1) {
    return n * factorial(n - 1);
  } else {
    return 1;
  }
}

int main() {
  cout << "5 ning faktoriali: " << factorial(5);
  return 0;
}

MA'LUMOT

Faktorial — sonni 1 gacha bo'lgan barcha kichik sonlarga ko'paytirishdir (masalan, 5 ning faktoriali: 5 × 4 × 3 × 2 × 1 = 120).