Java-da rekursiya

Rekursiya nima ekanligini tushunish uchun siz rekursiya nima ekanligini tushunishingiz kerak. Aslida, bunday funktsiyalarni tushunishda qiyin narsa yo'q, faqat bir marta yaxshi tushunishingiz kerak. Va dasturlash haqida gap ketganda mashq qiling. Java-da rekursiya - 1

Rekursiya nafaqat dasturlashda, balki real hayotda ham uchraydi. Qo'llaringizga oynani oling va boshqa oyna oldida turing. Ko'zguning aksi aks ettirishda aks etadi va hokazo. Siz cheksiz ko'p sonli ko'zgularning cheksizligini ko'rasiz. "Haqiqiy" rekursiya haqida ko'proq ma'lumotni " Groundhog kuniga bag'ishlangan ... " maqolasida topishingiz mumkin, keling, haqiqiy dunyodan dasturchining kundalik hayotiga qaytaylik. Oddiy ta'rif: java'da rekursiv funktsiyalar o'zlarini chaqiradigan funktsiyalardir. Sizga juda oddiy va juda zararli misol keltiraman:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Nima uchun zararli? Men buni o'zingiz tekshirishingizni maslahat beraman! Agar siz ushbu sarguzashtni boshdan kechirishga qaror qilsangiz (va siz, ehtimol, siz dasturchi!), JVM qanday xatoga yo'l qo'yishini izohlarda yozing =) Bu va boshqa ko'plab misollar Java-da rekursiyadan foydalanishga ehtiyotkorlik bilan yondashish kerakligini ko'rsatib beradi. . Muammoni hal qilishda bunday yondashuv qaerda, qachon va nima uchun oqlanishini tushunishingiz kerak va sizning funktsiyangiz dasturning bajarilishini "Groundhog Day" ga aylantirmasligiga ishonch hosil qilishingiz kerak. Rekursiyani tushunish uchun yana ikkita muhim ta'rif mavjud:

Rekursiya asosi - rekursiv chaqiruvlar blokidan chiqish sharti - rekursiyani chaqirishning hojati bo'lmagan sharoitlarda muammoning asosiy yechimi.
Rekursiya bosqichi - bu parametrlarni o'zgartirganda funktsiya o'zini chaqiradi.

Rekursiv funktsiyadan foydalanishning klassik misoli sonning faktorialini hisoblashdir. Agar unutgan bo'lsangiz, eslatib o'taman: musbat butun sonning faktoriali N(N bilan belgilanadi!) dan raqamlarning ko'paytmasidir 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Aytgancha, ta'rif bo'yicha nolning faktoriali 1 ga teng. Demak, faktorialni har qanday musbat butun va nol uchun topish mumkin (matematika tilida - manfiy bo'lmagan butun sonlar to'plami uchun yoki natural sonlar to'plami uchun va). nol). O'ylaymanki, siz looplar yordamida faktorial dasturlashingiz mumkinligini tushunasiz. Aslida, bu muammoni hal qilish uchun rekursiv bo'lmagan usul:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Raqamning musbat va butun son ekanligini tekshirishni va nol uchun alohida chekni qo'shamiz.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Endi men ushbu muammoni rekursiv hal qilish uchun usul kodini beraman:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Keling, qo'ng'iroqlar uchun chiqish natijalarini ko'rib chiqaylik:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Biz kutilgan qiymatlarni olamiz:

Keling, yaxshi natija qo'shamiz va kattaroq raqam uchun faktorialni hisoblaymiz:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Biz quyidagilarni olamiz: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Bunday holda, rekursiv funktsiyadan foydalanish asosli va xavfsizdir. Biz rekursiv blokdan chiqish shartini aniq belgilab oldik va bunga erishish mumkinligiga ishonchimiz komil: biz manfiy bo'lmagan butun sonni kiritamiz, agar raqam nolga yoki birga teng bo'lsa, natijani qaytaramiz, agar raqam katta bo'lsa. , natijani raqamning funktsiyasi bilan ko'paytiramiz n-1. Misol sifatida uchta faktorialdan foydalanish:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Foydalanishda ehtiyot bo'lish haqida: bu funktsiyaning zaifligi nimada? Agar siz usulga parametr sifatida manfiy raqam bersangiz, u holda tekshirish

if (n == 1 || n == 0) {
    return result;
}

hech qanday ma'no yo'q va biz o'zimizni chaqirishning cheksiz tsikliga tushib qolamiz. Salbiy emasligi uchun chekni qo'shishga arziydi:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

Va hammasi yaxshi bo'ladi.

Bir usulning boshqasidan qanday afzalligi bor? Bu unchalik katta farqga o‘xshamaydi, lekin aslida ko‘plab rekursiv qo‘ng‘iroqlar ishlash va xotira sarfiga salbiy ta’sir ko‘rsatadi: qo‘ng‘iroqlar to‘plami deyarli boshqarib bo‘lmaydigan manba bo‘lib, bir xil rekursiv funktsiyani chaqirish uchun turli sharoitlarda, biz ushbu resurs bilan bog'liq muammolarga duch kelishimiz yoki bo'lmasligimiz mumkin. Takrorlashlar yordamida yechilgan deyarli barcha masalalar (masalan, sikllar for-each) rekursiv tarzda ham echilishi mumkin. Rekursiyaning afzalligi - o'qish va yozish qulayligi, biz yuqorida kamchiliklar haqida gapirdik: "o'zingizni oyog'ingizga otish" imkoniyati xayoliy emas. “Murakkab rekursiya” deb ataladigan narsadan foydalanganda yanada ehtiyotkor bo'lishingiz kerak: Funktsiya funktsiyani chaqiradigan A()funktsiyani chaqiradi.Bunday muammolarni hal qilish rekursiya qanday ishlashini to'liq tushunishni talab qiladi. Bunday vazifaga misol: qiymatini hisoblash . Faktorial, yuqorida muhokama qilganimizdek, manfiy bo'lmagan butun sonlar to'plamida aniqlanadi. Nihoyat, men yechim kodini beraman. Murakkab rekursiya ikki usuldan iborat bo'ladi: B()A()x^n/(n!)

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Rekursiyani kiritish uchun usuldan foydalaniladi calculate, u usulni chaqiradi power, bu esa o'z navbatida usulni chaqiradi calculate. Biz kuch usulida rekursiya asosini aniqladik:

if (n == 1) return x;

U erda rekursiya bosqichi ham aniqlanadi:

return x * calculate(x, n - 1);

Kiritilgan ma'lumotlarning haqiqiyligini tekshirishni qo'shish qoladi:

Noldan boshqa har qanday raqam nolning kuchiga teng 1. Agar n = 0, keyin n! = 1. Uni qaytarish kerak 1.
Har qanday quvvat nol nolga teng.
Biz turdagi noaniqlikni hisobga olmaymiz 0^0va bunday kirish ma'lumotlarini yaroqsiz deb qabul qilamiz.

Barcha tekshiruvlar bilan usullar quyidagicha ko'rinadi:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Xo'sh, funktsiyaga qo'ng'iroq qilishda siz xatoni eslab qolishingiz kerak:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Izohlar

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION