C rekursiya

Rekursiya

Rekursiya — funksiyaning o‘zini o‘zi chaqirish usuli. Bu usul murakkab masalalarni hal qilish osonroq bo‘lgan oddiy masalalarga ajratish imkonini beradi.

Rekursiyani tushunish biroz qiyin bo‘lishi mumkin. Uning qanday ishlashini anglashning eng yaxshi yo‘li — u bilan tajriba o‘tkazish.

Rekursiya misoli

Ikki sonni qo‘shish oson, ammo sonlar oralig‘ini qo‘shish murakkabroq. Quyidagi misolda sonlar oralig‘ini qo‘shish uchun rekursiyadan foydalaniladi: vazifa ikki sonni qo‘shishdan iborat oddiy amalga ajratiladi:

int sum(int k);

int main() {
  int result = sum(10);
  printf("%d", result);
  return 0;
}

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

Misol izohi

sum() funksiyasi chaqirilganda, u k parametrini k qiymatidan kichik barcha sonlar yig‘indisiga qo‘shadi va natijani qaytaradi. k 0 ga teng bo‘lganda funksiya shunchaki 0 qaytaradi. Dastur ishga tushganda quyidagi qadamlarni bajaradi:

k 0 ga teng bo‘lganda funksiya o‘zini chaqirmagani uchun dastur shu yerda to‘xtaydi va natijani qaytaradi.

void countdown(int n);

int main() {
  countdown(5);
  return 0;
}

void countdown(int n) {
  if (n > 0) {
    printf("%d ", n);
    countdown(n - 1);
  }
}

Funksiya n qiymati 0 bo‘lguncha o‘zini n - 1 argumenti bilan chaqiradi.

Rekursiya yordamida faktorialni hisoblash

Bu misolda 5 ning faktorialini hisoblash uchun rekursiv funksiyadan foydalaniladi:

int factorial(int n);

int main() {
  printf("Factorial of 5 is %d", factorial(5));
  return 0;
}

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