Java rekursiya

Java rekursiya

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

Rekursiyani tushunish biroz qiyin bo‘lishi mumkin. Uning qanday ishlashini tushunishning eng yaxshi yo‘li — u bilan tajriba qilib ko‘rish.

Rekursiya misoli

Ikkita sonni qo‘shish oson, ammo sonlar oralig‘ini qo‘shish murakkabroq. Quyidagi misolda sonlar oralig‘ini qo‘shish uchun rekursiyadan foydalaniladi: vazifa ikkita sonni qo‘shishdan iborat oddiy vazifaga ajratiladi:

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

  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
}

Misol izohi

sum() metodi chaqirilganda u k parametrini k’dan kichik barcha sonlar yig‘indisiga qo‘shadi va natijani qaytaradi. k 0 ga teng bo‘lganda metod shunchaki 0 qaytaradi. Dastur ishlaganda quyidagi qadamlarni bajaradi:

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

To‘xtash sharti

Sikllar cheksiz takrorlanish muammosiga duch kelishi mumkin bo‘lgani kabi, rekursiv metodlar ham cheksiz rekursiya muammosiga duch kelishi mumkin. Cheksiz rekursiya — metodning o‘zini chaqirishni hech qachon to‘xtatmasligi. Har bir rekursiv metodda to‘xtash sharti bo‘lishi kerak — bu metod o‘zini chaqirishni to‘xtatadigan shartdir. Oldingi misolda to‘xtash sharti — k parametrining 0 ga teng bo‘lishi.

Tushunchani yaxshiroq anglash uchun turli xil misollarni ko‘rib chiqish foydali. Bu misolda metod boshlang‘ich va oxirgi qiymat orasidagi sonlar oralig‘ini qo‘shadi. Bu rekursiv metodning to‘xtash sharti — end qiymati start qiymatidan katta bo‘lmay qolishi:

public class Main {
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }

  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
}

Rekursiya yordamida teskari sanash

Bu misol teskari sanash funksiyasini yaratish uchun rekursiyadan qanday foydalanishni ko‘rsatadi:

public class Main {
  static void countdown(int n) {
    if (n > 0) {
      System.out.print(n + " ");
      countdown(n - 1);
    }
  }

  public static void main(String[] args) {
    countdown(5);
  }
}

Metod n qiymati 0’ga yetguncha o‘zini n - 1 argumenti bilan chaqiraveradi.

Rekursiya yordamida faktorialni hisoblash

Bu misolda 5 ning faktorialini hisoblash uchun rekursiv metoddan foydalaniladi:

public class Main {
  static int factorial(int n) {
    if (n > 1) {
      return n * factorial(n - 1);
    } else {
      return 1;
    }
  }

  public static void main(String[] args) {
    System.out.println("Factorial of 5 is " + factorial(5));
  }
}