Chiqish shartsiz rekursiya kodiga misol
Qani qaytadan rekursiv vazifaga qaraylik. Masalan, Fibonachchi sonlarini izlashni ko'rib chiqamiz. Kim eslamasa, Fibonachchi ketma-ketligi - sonlar ketma-ketligining elementlari, bunda birinchi ikkita son 0 va 1 ga teng, va har bir keyingi son oldingi ikki sonning yig'indisiga teng.
Bunday sonlarni topish va ko'rsatish uchun kod yozamiz:
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacci(0, 1);
}
private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}
}
Rekursiv metodni birinchi chaqirishdan oldin printFibonacci, ketma-ketlikning birinchi ikkita sonini chiqaramiz – nol va birlik. Bu kerak, chunki rekursiv metodda biz faqat parametrlarning yig'indisini chiqaramiz, o'zlari emas.
Barchasi yaxshi ko'rinadi: ikki sonni olamiz, ularning yig'indisini hisoblaymiz, uni konsolda chiqaramiz, va yana rekursiv metod printFibonaccini chaqiramiz. Parametrlar sifatida oldingi (previous) va joriy sonni (current) o'tkazamiz.
Aslida bu kodda 2 xato bor. Ularni kodni ishga tushirganda sezish mumkin.
Birinchi xato long tipining to'lishida. Bizning ketma-ketligimizning 104-soni manfiy bo'lib ko'rsatildi, bu long tipining to'lganligini anglatadi.
Ikkinchi xato boshqa tabiatga ega. 12 mingdan ortiq son topilgandan so'ng, ekranda quyidagilar chiqadi:
Bu yerda metod chaqiruvlari steki nima ekanligini eslash o'rinli. Java mashinasida barcha funksiyalarning chaqiruvlarini yozib boradigan maxsus kolleksiya – stek bor. Bir funksiyaning boshqa birini chaqirishi bilan Java mashinasi bu stekka yangi element StackTraceElement joylashtiradi. Funksiya tugaganda esa bu element stekdan o'chiriladi. Natijada bu stekda doim "funksiyalarning chaqiruvlari steki"ning dolzarb holati saqlanadi. StackOverflowError xatosining so'zma-so'z tarjimasi – "stek to'ldi". Javadocda shunday yozilgan: "Stek chaqiruvi juda chuqur bo'lganda tashlanadi". Ishga tushgan JVMda stek chaqiruvlarini saqlash uchun maxsus xotira maydoni mavjud. Bu xotira maydonining o'lchami OS va JVM sozlamalariga bog'liq. Chaqiruvlar stekidan tashqari bu xotira maydonida primitiv o'zgaruvchilar (metod chaqiruvi parametrlarining aniq qiymatlari) va ko'rsatuv o'zgaruvchilarning manzillari (HEAP xotira maydonida) saqlanadi. Stekka kirish modeli – LIFO.
Chiqish sharti bilan tuzatilgan misol
Kodimizni tuzatishni ikkinchi muammodan boshlaymiz.
Muammoni to'g'ridan-to'g'ri hal qilishga urinib ko'ramiz: agar stekning o'lchami kichik bo'lsa, uni kattalashtiramiz. Buning uchun JVMni maxsus -Xss flag bilan ishga tushirish kerak va stek uchun qancha xotira ajratishni belgilash kerak. IDEAda bu shunday ko'rinishga ega bo'ladi:
Ha, chiqishning uzunligi oshdi va endi bu 12+ ming topilgan sonlar ketma-ketligi emas, balki 49+ ming. Lekin qandaydir sondan keyin yana StackOverflowError olamiz.
Stek xotira maydonini yana ham kengaytirib ko'rish mumkin, lekin bu prinsipial jihatdan hech narsani o'zgartirmaydi. Demak, muammoni logikada qidiramiz. Rekursiyada to'xtash nuqtasi bo'lishi kerak. Rekursiv metod chaqirilmaydigan va stek chaqiruvlar qaytadigan qandaydir shart bo'lishi kerak. Bunday shartni aniqlash uchun, vazifani aniqroq qilamiz – Fibonachchi sonlar ketma-ketligini Integer.MAX_VALUEdan kichik bo'lgan paytgacha chiqaramiz.
Bu shartni inobatga oluvchi yangi printFibonacciWithCondition metodini yozamiz. Va asosiy metodda aynan shu yangi to'g'irlangan metodni chaqiramiz.
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
// printFibonacci(0, 1);
printFibonacciWithCondition(0, 1);
}
private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
System.out.println(current);
printFibonacciWithCondition(previous, current);
}
}
Kodni ishga tushirgandan so'ng haqiqatan ham 1836311903 soni bilan yakunlanganini ko'ramiz. Bu son bilan 1134903170 soni oldin kelgan edi. Ularning yig'indisi 2_971_215_073, bu esa haqiqatan ham Integer.MAX_VALUE (2_147_483_647)dan kattaroq.
Bu tuzatish bilan bizda avtomatik ravishda long tipining to'lish xatosi tuzatiladi. Agar uzunroq sonlar ketma-ketligi kerak bo'lsa, boshqa ma'lumot turlaridan foydalanish kerak, masalan, BigInteger.
Rekursiv tushirish va qaytish metodi
Kodimiz qanday ishlashini bosqichma-bosqich tahlil qilib chiqamiz. Buning uchun echo metodini qo'shamiz va uni printFibonacciWithCondition rekursiv chaqiruvi oldida va keyin chaqiramiz.
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacciWithCondition(0, 1);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
echo(true, penultimate, previous);
System.out.println(current);
printFibonacciWithCondition(previous, current);
echo(false, penultimate, previous);
}
private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
if (isBeforeRecursiveCall) {
System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
} else {
System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
}
}
}
Dastur natijasini quyidagicha olamiz:
1
Before method call with args: 0, 1. Current number = 1
Before method call with args: 1, 1. Current number = 2
Before method call with args: 1, 2. Current number = 3
Before method call with args: 2, 3. Current number = 5
Before method call with args: 3, 5. Current number = 8
Before method call with args: 5, 8. Current number = 13
Before method call with args: 8, 13. Current number = 21
Before method call with args: 13, 21. Current number = 34
Before method call with args: 21, 34. Current number = 55
Before method call with args: 34, 55. Current number = 89
Before method call with args: 55, 89. Current number = 144
Before method call with args: 89, 144. Current number = 233
Before method call with args: 144, 233. Current number = 377
Before method call with args: 233, 377. Current number = 610
Before method call with args: 377, 610. Current number = 987
Before method call with args: 610, 987. Current number = 1597
Before method call with args: 987, 1597. Current number = 2584
Before method call with args: 1597, 2584. Current number = 4181
Before method call with args: 2584, 4181. Current number = 6765
Before method call with args: 4181, 6765. Current number = 10946
Before method call with args: 6765, 10946. Current number = 17711
Before method call with args: 10946, 17711. Current number = 28657
Before method call with args: 17711, 28657. Current number = 46368
Before method call with args: 28657, 46368. Current number = 75025
Before method call with args: 46368, 75025. Current number = 121393
Before method call with args: 75025, 121393. Current number = 196418
Before method call with args: 121393, 196418. Current number = 317811
Before method call with args: 196418, 317811. Current number = 514229
Before method call with args: 317811, 514229. Current number = 832040
Before method call with args: 514229, 832040. Current number = 1346269
Before method call with args: 832040, 1346269. Current number = 2178309
Before method call with args: 1346269, 2178309. Current number = 3524578
Before method call with args: 2178309, 3524578. Current number = 5702887
Before method call with args: 3524578, 5702887. Current number = 9227465
Before method call with args: 5702887, 9227465. Current number = 14930352
Before method call with args: 9227465, 14930352. Current number = 24157817
Before method call with args: 14930352, 24157817. Current number = 39088169
Before method call with args: 24157817, 39088169. Current number = 63245986
Before method call with args: 39088169, 63245986. Current number = 102334155
Before method call with args: 63245986, 102334155. Current number = 165580141
Before method call with args: 102334155, 165580141. Current number = 267914296
Before method call with args: 165580141, 267914296. Current number = 433494437
Before method call with args: 267914296, 433494437. Current number = 701408733
Before method call with args: 433494437, 701408733. Current number = 1134903170
Before method call with args: 701408733, 1134903170. Current number = 1836311903
After method call with args: 701408733, 113490317
After method call with args: 433494437, 701408733
After method call with args: 267914296, 433494437
After method call with args: 165580141, 267914296
After method call with args: 102334155, 165580141
After method call with args: 63245986, 102334155
After method call with args: 39088169, 63245986
After method call with args: 24157817, 39088169
After method call with args: 14930352, 24157817
After method call with args: 9227465, 14930352
After method call with args: 5702887, 9227465
After method call with args: 3524578, 5702887
After method call with args: 2178309, 3524578
After method call with args: 1346269, 2178309
After method call with args: 832040, 1346269
After method call with args: 514229, 832040
After method call with args: 317811, 514229
After method call with args: 196418, 317811
After method call with args: 121393, 196418
After method call with args: 75025, 121393
After method call with args: 46368, 75025
After method call with args: 28657, 46368
After method call with args: 17711, 28657
After method call with args: 10946, 17711
After method call with args: 6765, 10946
After method call with args: 4181, 6765
After method call with args: 2584, 4181
After method call with args: 1597, 2584
After method call with args: 987, 1597
After method call with args: 610, 987
After method call with args: 377, 610
After method call with args: 233, 377
After method call with args: 144, 233
After method call with args: 89, 144
After method call with args: 55, 89
After method call with args: 34, 55
After method call with args: 21, 34
After method call with args: 13, 21
After method call with args: 8, 13
After method call with args: 5, 8
After method call with args: 3, 5
After method call with args: 2, 3
After method call with args: 1, 2
After method call with args: 1, 1
After method call with args: 0, 1
Bu jarayonni grafik tarzda tasvirlab beramiz.
Yana bir marta birga ko'rib chiqamiz: printFibonacciWithCondition metodi chaqiriladi. Unda joriy son hisoblanadi. Agar bu bizga mos kelsa, uni chiqaramiz va yana yangi parametrlar bilan printFibonacciWithCondition metodini chaqiramiz.
Rekursiv metod chaqiruvi davomida – bu "Rekursiv tushish" deb ataladi. Chaqiruv steki orqali qaytish – "Rekursiv qaytish" deb ataladi.
Rekursiya – dasturlashda qiziqarli mavzu. Materialni yaxshiroq o'rganish uchun vazifani biroz o'zgartiramiz. Fibonachchi sonlar ketma-ketligini Integer.MAX_VALUEni oshib ketmaganlarida kamayish tartibida chiqarish kerak. Bu vazifani hal qilish uchun biz allaqachon butun kodni yozib bo'ldik. Qolgan narsa – findeswọz:current chiqish joylarini va rekursiv metod chaqiruvini joylarini o'zgartirish. Ya'ni, birinchi misolda topilgan sonning chiqarilishi "tushish bosqichida" ro'y berdi, endi esa "eng pastga tushishni" va "qaytish bosqichida" sonlarni chiqarishni kerak. Va albatta, asosiy metodda ketma-ketlikning boshlang'ich ikki sonini (nol va birlik) joylarini o'zgartiring va rekursiv metod chaqiruvidan keyin chiqarib turing. O'qilishi uchun echo metodini olib tashlaymiz.
public class Fibonacci {
public static void main(String[] args) {
printFibonacciWithCondition(0, 1);
System.out.println(1);
System.out.println(0);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
printFibonacciWithCondition(previous, current);
System.out.println(current);
}
}
Chiqish quyidagicha bo'ladi:
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0
GO TO FULL VERSION