నిష్క్రమణ పరిస్థితి లేకుండా పునరావృత కోడ్ యొక్క ఉదాహరణ
పునరావృత సమస్య గురించి మరొకసారి చూద్దాం. ఉదాహరణగా, ఫైబొనాక్సీ సంఖ్యలను లెక్కించడాన్ని పరిగణించండి. ఫిబొనాక్సీ సీక్వెన్స్ అనేది మొదటి రెండు సంఖ్యలు 0 మరియు 1 అనే సంఖ్యా శ్రేణి అని మరియు ప్రతి తదుపరి సంఖ్య మునుపటి రెండు సంఖ్యల మొత్తానికి సమానం అని అందరూ గుర్తుంచుకుంటారు.
ఈ సంఖ్యలను లెక్కించడానికి మరియు ప్రదర్శించడానికి కోడ్ వ్రాద్దాం:
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);
}
}
పునరావృత ప్రింట్ఫైబొనాక్సీ పద్ధతి యొక్క మొదటి కాల్కు ముందు , క్రమం యొక్క మొదటి రెండు సంఖ్యలను ముద్రించండి: సున్నా మరియు ఒకటి. రికర్సివ్ పద్ధతి ఇన్పుట్ పారామితుల మొత్తాన్ని మాత్రమే ప్రదర్శిస్తుంది, పారామితులు కాకుండా మనం దీన్ని చేయాలి.
కోడ్ బాగానే ఉంది: మేము రెండు సంఖ్యలను పొందుతాము, వాటి మొత్తాన్ని లెక్కించండి, దానిని కన్సోల్లో ముద్రించండి మరియు printFibonacci పద్ధతిని పునరావృతంగా మళ్లీ కాల్ చేస్తాము. మేము మునుపటి సంఖ్యను (మునుపటి) మరియు ప్రస్తుత సంఖ్యను (ప్రస్తుతం) ఆర్గ్యుమెంట్లుగా పాస్ చేస్తాము.
వాస్తవానికి, కోడ్లో రెండు లోపాలు ఉన్నాయి. మీరు కోడ్ని అమలు చేస్తే వాటిని చూడవచ్చు.
మొదటి ఎర్రర్ లాంగ్ టైప్ ఓవర్ఫ్లో కావడం. మా సీక్వెన్స్లోని 104వ సంఖ్య ప్రతికూలంగా ఉంది, ఇది పొడవైన రకం పొంగిపొర్లిందని సూచిస్తుంది.
రెండవ లోపం భిన్నంగా ఉంటుంది. సుమారు 12,000 సంఖ్యలను లెక్కించిన తర్వాత, మనకు లభిస్తుంది:
జావాలో కాల్ స్టాక్ పద్ధతి ఏమిటో గుర్తుకు తెచ్చుకోవడానికి ఇప్పుడు సరైన సమయం. జావా మెషీన్ అన్ని ఫంక్షన్ కాల్ల రికార్డును ఉంచుతుంది. దీన్ని చేయడానికి, ఇది స్టాక్ అని పిలువబడే ప్రత్యేక రకమైన సేకరణను ఉపయోగిస్తుంది. ఒక ఫంక్షన్ మరొకదానికి కాల్ చేసినప్పుడు, జావా మెషీన్ కొత్త StackTraceElementని స్టాక్పైకి నెట్టివేస్తుంది. ఫంక్షన్ ముగిసినప్పుడు, ఈ మూలకం స్టాక్ నుండి తీసివేయబడుతుంది. దీని ప్రకారం, స్టాక్ ఎల్లప్పుడూ ఫంక్షన్ కాల్ స్టాక్ యొక్క ప్రస్తుత స్థితి గురించి తాజా సమాచారాన్ని నిల్వ చేస్తుంది. StackTraceElement కోసం డాక్యుమెంటేషన్ అది "ఒక అప్లికేషన్ చాలా లోతుగా పునరావృతం అయినందున స్టాక్ ఓవర్ఫ్లో సంభవించినప్పుడు విసిరివేయబడుతుంది" అని చెప్పింది. నడుస్తున్న JVM మెథడ్ కాల్ స్టాక్ను నిల్వ చేయడానికి ప్రత్యేక మెమరీని కలిగి ఉంటుంది. ఈ మెమరీ ప్రాంతం యొక్క పరిమాణం OS మరియు JVM సెట్టింగ్లపై ఆధారపడి ఉంటుంది. పద్ధతి కాల్ స్టాక్తో పాటు, ఆదిమ వేరియబుల్స్ (పద్ధతి పారామితుల యొక్క నిర్దిష్ట విలువలు) మరియు రిఫరెన్స్ వేరియబుల్స్ చిరునామాలు ("హీప్" అని పిలువబడే మెమరీ ప్రాంతంలో) ఈ ప్రత్యేక మెమరీ ప్రాంతంలో నిల్వ చేయబడతాయి. కాల్ స్టాక్కు యాక్సెస్ LIFO సూత్రాన్ని అనుసరిస్తుంది.
నిష్క్రమణ పరిస్థితితో సరిదిద్దబడిన ఉదాహరణ
కోడ్లోని రెండవ సమస్యను పరిష్కరించడం ద్వారా ప్రారంభిద్దాం.
సమస్యను పరిష్కరించడానికి ప్రయత్నిద్దాం: స్టాక్ చాలా చిన్నగా ఉంటే, దానిని పెద్దదిగా చేద్దాం. దీన్ని చేయడానికి, "-Xss" ఫ్లాగ్తో JVMని ప్రారంభించండి మరియు స్టాక్ కోసం ఎంత మెమరీని కేటాయించాలో పేర్కొనండి. 5 మెగాబైట్లను కేటాయించడానికి ప్రయత్నిద్దాం. IDEAలో ఇది ఇలా ఉంటుంది:
మేము అవుట్పుట్ పొడవును పెంచగలిగాము. ఇప్పుడు 12,000 సంఖ్యలకు పరిమితం కాకుండా 49,000 కంటే ఎక్కువ వరుస సంఖ్యలను లెక్కించవచ్చు. కానీ ఏదో ఒక సమయంలో, మనకు ఇప్పటికీ StackOverflowError వస్తుంది .
మీరు స్టాక్ పరిమాణాన్ని పెంచడానికి ప్రయత్నించవచ్చు, కానీ అది ప్రాథమిక సమస్యను పరిష్కరించదు. కాబట్టి, తర్కంలో సమస్య కోసం చూద్దాం. పునరావృతం ఆగిపోయినప్పుడు తప్పనిసరిగా ఒక పాయింట్ ఉండాలి. మరో మాటలో చెప్పాలంటే, రికర్సివ్ పద్ధతిని ఎప్పుడు పిలవకూడదో నిర్ణయించే కొన్ని షరతు ఉండాలి, ఇది కాల్ స్టాక్ను నిలిపివేయడానికి అనుమతిస్తుంది. అటువంటి షరతును నిర్వచించడానికి, మన లక్ష్యాన్ని స్పష్టంగా తెలియజేస్తాము: ఫిబొనాక్సీ సిరీస్ సంఖ్యలు పూర్ణాంకం కంటే తక్కువగా ఉన్నంత వరకు ప్రదర్శించండి. MAX_VALUE .
ఈ షరతును పరిగణనలోకి తీసుకునే కొత్త printFibonacciWithCondition పద్ధతిని వ్రాద్దాం . మరియు మేము ప్రధాన పద్ధతిలో కొత్త సరిదిద్దబడిన పద్ధతిని పిలుస్తాము.
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);
}
}
కోడ్ని అమలు చేసిన తర్వాత, అవుట్పుట్ 1836311903 సంఖ్యతో ముగుస్తుందని మేము చూస్తాము. దీనికి ముందు ఉన్న సంఖ్య 1134903170. ఈ సంఖ్యల మొత్తం 2_971_215_073, ఇది నిజానికి పూర్ణాంకం కంటే ఎక్కువ.MAX_VALUE (2_164_78 ) .
ఈ మార్పు స్వయంచాలకంగా సుదీర్ఘ ఓవర్ఫ్లో బగ్ను పరిష్కరించింది . మీరు మరిన్ని సిరీస్లను లెక్కించాలనుకుంటే, మీరు BigInteger వంటి ఇతర డేటా రకాలను ఉపయోగించాల్సి ఉంటుంది .
పునరావృత అవరోహణ మరియు అన్వైండింగ్
మన కోడ్ ఎలా అమలు చేయబడుతుందో దశలవారీగా విశ్లేషిద్దాం. దీన్ని చేయడానికి, మేము ఎకో పద్ధతిని జోడిస్తాము మరియు printFibonacciWithCondition పద్ధతి యొక్క పునరావృత కాల్కు ముందు మరియు తర్వాత కాల్ చేస్తాము .
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);
}
}
}
ప్రోగ్రామ్ మాకు ఈ అవుట్పుట్ ఇస్తుంది:
1
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 0, 1. ప్రస్తుత నంబర్ = 1
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 1, 1. ప్రస్తుత నంబర్ = 2
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 1, 2. ప్రస్తుత నంబర్ = 3
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 2, 3. ప్రస్తుత సంఖ్య = 5
ఆర్గ్లతో పద్ధతి కాల్కు ముందు: 3, 5. ప్రస్తుత సంఖ్య = 8
ఆర్గ్లతో పద్ధతి కాల్కు ముందు: 5, 8. ప్రస్తుత సంఖ్య = 13
ఆర్గ్లతో పద్ధతి కాల్కు ముందు: 8, 13. ప్రస్తుత సంఖ్య = 21
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 13, 21. ప్రస్తుత నంబర్ = 34
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 21, 34. ప్రస్తుత నంబర్ = 55
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 34, 55. ప్రస్తుత నంబర్ = 89 ఆర్గ్లతో
మెథడ్ కాల్కు ముందు: 55, 89. ప్రస్తుత సంఖ్య = 144
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 89, 144. ప్రస్తుత నంబర్ = 233
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 144, 233. ప్రస్తుత నంబర్ = 377
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 233, 377. ప్రస్తుత నంబర్ = 610
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 377 610. ప్రస్తుత నంబర్ = 987
ఆర్గ్స్తో మెథడ్ కాల్కు ముందు: 610, 987. ప్రస్తుత నంబర్ = 1597
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 987, 1597. ప్రస్తుత నంబర్ = 2584
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 1597, 2584
ముందు పద్ధతి = 418 ఆర్గ్లతో కాల్ చేయండి: 2584, 4181. ప్రస్తుత నంబర్ = 6765
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 4181, 6765. ప్రస్తుత నంబర్ = 10946
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 6765, 10946. ప్రస్తుత నంబర్ = 17711 1
పద్ధతికి ముందు 1 ప్రస్తుత సంఖ్య = 28657
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 17711, 28657. ప్రస్తుత నంబర్ = 46368
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 28657, 46368. ప్రస్తుత నంబర్ = 75025 ఆర్గ్లతో మెథడ్ కాల్కు ముందు
: 46368, 75025. 1213 మెథడ్ 9కి ముందు
121393. ప్రస్తుత నంబర్ = 196418
argsతో పద్ధతికి ముందు కాల్: 121393, 196418. ప్రస్తుత నంబర్ = 317811
argsతో పద్ధతికి ముందు కాల్: 196418, 317811. ప్రస్తుత నంబర్ = 514227
args పద్ధతికి ముందు: 5143129 పద్ధతికి 41 సంఖ్య = 832040
పద్ధతికి ముందు ఆర్గ్లతో కాల్ చేయండి: 514229, 832040. ప్రస్తుత నంబర్ = 1346269
పద్ధతికి ముందు ఆర్గ్లతో కాల్ చేయండి: 832040, 1346269.
ప్రస్తుత నంబర్ = 2178309 ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 13462830, 735 2175
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 2178309, 3524578. ప్రస్తుత నంబర్ = 5702887
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 3524578, 5702887. ప్రస్తుత నంబర్ = 9227465 ఆర్గ్లతో
మెథడ్ కాల్కు ముందు: 5650287 రెంట్ = 560287
ఆర్గ్స్తో మెథడ్ కాల్: 9227465, 14930352. కరెంట్ నంబర్ = 24157817
బిఫోర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 14930352, 24157817. ప్రస్తుత నంబర్ = 39088169
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 24157817, 39088169కి ముందు 39088169 పద్ధతితో కాల్ చేయండి: 39088169. 088169
, 63245986. ప్రస్తుత సంఖ్య = 102334155
పద్ధతికి ముందు ఆర్గ్లతో కాల్ చేయండి: 63245986, 102334155. ప్రస్తుత నంబర్ = 165580141
పద్ధతికి ముందు ఆర్గ్లతో కాల్ చేయండి: 102334155, 165580141. ప్రస్తుత నంబర్ = 267914296
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 165580141, 267914296. ప్రస్తుత నంబర్ = 433494437
ఆర్గ్లతో మెథడ్ కాల్కు ముందు: 267914296, 433494437. ప్రస్తుత నంబర్ = 701408734 మెథడ్
కాల్కి ముందు 701408734 . ప్రస్తుత నంబర్ = 1134903170
పద్ధతికి ముందు ఆర్గ్లతో కాల్ చేయండి: 701408733, 1134903170. ప్రస్తుత నంబర్ = 1836311903
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 701408733, 113490317
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 433494437, 701408733 ఆఫ్టర్ మెథడ్ కాల్ విత్ 601408733 ఆఫ్టర్ మెథడ్
కాల్ విత్ 66908733 args
: 165580141, 267914296
పద్ధతి తర్వాత argsతో కాల్ చేయండి: 102334155, 165580141
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్స్: 63245986, 102334155
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 39088169, 63245986
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 24157817, 39088169
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 14930352, 24157817
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 9227465, 14930352 ఆఫ్టర్ మెథడ్ కాల్
విత్ ఆర్గ్లు: 745 తర్వాత మెథడ్ కాల్ విత్ ఆర్గ్లు
: 745 తర్వాత 28,57028 4578, 5702887
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్స్ : 2178309, 3524578
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 1346269, 2178309
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 832040, 1346269
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 514229, 832040 ఆఫ్టర్
మెథడ్ కాల్ విత్ 514229, 832040
ఆఫ్టర్ మెథడ్ కాల్ విత్ 35 ఆర్గ్స్: 196418, 317811
తర్వాత మెథడ్ కాల్ విత్ ఆర్గ్స్: 121393, 196418
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్స్: 75025, 121393
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 46368, 75025
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 28657, 46368
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 17711, 28657
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 10946, 17711 ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు:
6765, 10946
ఆఫ్టర్ మెథడ్ కాల్ విత్ 6181, 6181
ఆర్గ్స్ తర్వాత మెథడ్ కాల్ : 2584, 4181
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 1597, 2584
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్స్: 987, 1597
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 610, 987
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 377, 610 ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 377, 610 ఆఫ్టర్ మెథడ్ కాల్ విత్ 7
, 33
ఆర్గ్లతో మెథడ్ కాల్: 144, 233
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 89, 144
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 55, 89
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 34, 55
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 21, 34
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 13, 21
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 8, 13
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 5, 8
ఆఫ్టర్ మెథడ్ కాల్ విత్ ఆర్గ్లు: 3, 5
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 2, 3
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత : 1, 2
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 1, 1
ఆర్గ్లతో మెథడ్ కాల్ తర్వాత: 0, 1
ఇక్కడ ఏమి జరుగుతుందో విజువలైజేషన్ ఉంది.
మళ్ళీ చెప్పుకుందాం: printFibonacciWithCondition పద్ధతి అంటారు. ఇది ప్రస్తుత సంఖ్యను గణిస్తుంది. ఇది మాకు సరిపోతుంటే, మేము దానిని ప్రదర్శిస్తాము మరియు కొత్త వాదనలతో మళ్లీ printFibonacciWithCondition పద్ధతిని కాల్ చేస్తాము.
రికర్సివ్ పద్ధతి అని పిలువబడుతున్నంత కాలం, దీనిని "పునరావృత అవరోహణ" అంటారు. పునరావృత ముగింపులు మరియు పద్ధతి కాల్లు తిరిగి వచ్చినప్పుడు, మేము కాల్ స్టాక్ "అన్వైండింగ్" అని చెబుతాము.
ప్రోగ్రామింగ్లో రికర్షన్ అనేది ఒక ఆసక్తికరమైన అంశం. మెటీరియల్పై మెరుగైన హ్యాండిల్ పొందడానికి, మన పనిని కొద్దిగా మార్చుకుందాం. ఫిబొనాక్సీ సిరీస్లోని పూర్ణాంకానికి మించని అన్ని సంఖ్యలను అవరోహణ క్రమంలో అవుట్పుట్ చేయడం కొత్త పని. MAX_VALUE . మేము ఇప్పటికే ఈ టాస్క్కి అవసరమైన అన్ని కోడ్లను వ్రాసాము. ప్రస్తుత సంఖ్యను ప్రదర్శించే మరియు పునరావృత పద్ధతికి కాల్ చేసే క్రమాన్ని మార్చుకోవడం మాత్రమే మిగిలి ఉంది. అంటే, మొదటి ఉదాహరణలో, లెక్కించిన సంఖ్య "అవరోహణ" సమయంలో ప్రదర్శించబడుతుంది, కానీ ఇప్పుడు మనం "చాలా దిగువకు దిగి" ఆపై "బ్యాక్ అప్ మార్గంలో" సంఖ్యలను ప్రదర్శించాలి. మరియు వాస్తవానికి, ప్రధాన పద్ధతిలో , మేము పునరావృత పద్ధతిని పిలిచిన తర్వాత వాటిని ప్రదర్శించిన తర్వాత సీక్వెన్స్ (సున్నా మరియు ఒకటి) యొక్క రెండు ప్రారంభ సంఖ్యలను మార్పిడి చేస్తాము. చదవడానికి,పద్ధతి.
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);
}
}
అవుట్పుట్ ఇలా ఉంటుంది:
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