Exemplu de cod recursiv fără o condiție de ieșire
Să aruncăm o altă privire asupra unei probleme recursive. Ca exemplu, luați în considerare calcularea numerelor Fibonacci. Toată lumea își va aminti că șirul Fibonacci este o succesiune numerică în care primele două numere sunt 0 și 1, iar fiecare număr următor este egal cu suma celor două numere anterioare.
Să scriem cod pentru a calcula și afișa aceste numere:
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);
}
}
Înainte de primul apel al metodei recursive printFibonacci , imprimați primele două numere ale secvenței: zero și unu. Trebuie să facem acest lucru deoarece metoda recursivă afișează doar suma parametrilor de intrare, nu parametrii înșiși.
Codul arată în regulă: obținem două numere, calculăm suma lor, o imprimăm pe consolă și apelăm recursiv metoda printFibonacci din nou. Trecem ca argumente numărul anterior (anterior) și numărul curent (actual).
De fapt, codul are două erori. Le puteți vedea dacă rulați codul.
Prima eroare este debordarea tipului lung . Al 104-lea număr din secvența noastră este negativ, ceea ce indică faptul că tipul lung a debordat.
A doua eroare este diferită. După calcularea a aproximativ 12.000 de numere, obținem:
Acum este un moment potrivit pentru a ne aminti ce este o stivă de apeluri de metodă în Java. Mașina Java păstrează o evidență a tuturor apelurilor de funcții. Pentru a face acest lucru, folosește un tip special de colecție numită stivă. Când o funcție o apelează pe alta, mașina Java împinge un nou StackTraceElement în stivă. Când funcția se termină, acest element este eliminat din stivă. În consecință, stiva stochează întotdeauna informații actualizate despre starea curentă a stivei de apeluri de funcție. Documentația pentru StackTraceElement spune că este „Aruncat atunci când are loc o depășire a stivei, deoarece o aplicație recurge prea profund”. Un JVM care rulează are o zonă specială de memorie pentru stocarea stivei de apeluri de metodă. Mărimea acestei zone de memorie depinde de setările sistemului de operare și JVM. În plus față de stiva de apeluri de metodă în sine, variabilele primitive (valori specifice ale parametrilor metodei) și adresele variabilelor de referință (într-o zonă de memorie numită „heap”) sunt stocate în această zonă de memorie specială. Accesul la stiva de apeluri urmează principiul LIFO.
Exemplu corectat cu o condiție de ieșire
Să începem prin a remedia a doua problemă din cod.
Să încercăm să rezolvăm problema direct: dacă stiva este prea mică, atunci hai să o facem mai mare. Pentru a face acest lucru, porniți JVM-ul cu indicatorul „-Xss” și specificați câtă memorie să alocați pentru stivă. Să încercăm să alocăm 5 megaocteți. Iată cum va arăta în IDEA:
Am reușit să creștem lungimea ieșirii. Acum se pot calcula mai mult de 49.000 de numere ale secvenței, în loc să fie limitat la aproximativ 12.000 de numere. Dar, la un moment dat, încă primim o StackOverflowError .
Puteți încerca să măriți dimensiunea stivei, dar asta nu rezolvă problema fundamentală. Deci, să căutăm o problemă de logică. Trebuie să existe un moment în care recursiunea se oprește. Cu alte cuvinte, trebuie să existe o condiție care să determine când metoda recursivă nu va mai fi apelată, permițând stivei de apeluri să se deruleze. Pentru a defini o astfel de condiție, să explicăm obiectivul nostru: afișați seria Fibonacci atâta timp cât numerele sale sunt mai mici decât Integer.MAX_VALUE .
Să scriem o nouă metodă printFibonacciWithCondition care va ține cont de această condiție. Și vom numi noua metodă corectată în metoda principală.
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);
}
}
După rularea codului, vedem că rezultatul se termină cu numărul 1836311903. Numărul înainte de acesta este 1134903170. Suma acestor numere este 2_971_215_073, care este într-adevăr mai mare decât Integer.MAX_VALUE (2_147_483_647 ) .
Această modificare a remediat automat bug-ul de overflow lung . Dacă trebuie să calculați mai mult din serie, va trebui să utilizați alte tipuri de date, cum ar fi BigInteger .
Coborâre recursive și relaxare
Să analizăm pas cu pas cum este executat codul nostru. Pentru a face acest lucru, vom adăuga o metodă echo și o vom apela înainte și după apelul recursiv al metodei 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);
}
}
}
Programul ne oferă această ieșire:
1
Înainte de apelarea metodei cu argumente: 0, 1. Număr curent = 1
Înainte de apelarea metodei cu argumente: 1, 1. Număr curent = 2
Înainte de apelarea metodei cu argumente: 1, 2. Număr curent = 3
Înainte de apelarea metodei cu argumente: 2, 3. Număr curent = 5
Înainte de apelul metodei cu argumente: 3, 5. Număr curent = 8
Înainte de apelul metodei cu argumente: 5, 8. Număr curent = 13
Înainte de apelul metodei cu argumente: 8, 13. Număr curent = 21
Înainte de apelul de metodă cu argumente: 13, 21. Număr curent = 34
Înainte de apelul de metodă cu argumente: 21, 34. Număr curent = 55
Înainte de apelul de metodă cu argumente: 34, 55. Număr curent = 89
Înainte de apelul de metodă cu argumente: 55, 89. Numărul curent = 144
Înainte de apelul de metodă cu argumente: 89, 144. Număr curent = 233
Înainte de apelul de metodă cu argumente: 144, 233. Număr curent = 377
Înainte de apelul de metodă cu argumente: 233, 377. Număr curent = 610
Înainte de apelul de metodă cu argumente: 377, 610. Număr curent = 987
Înainte de apelul metodei cu argumente: 610, 987. Număr curent = 1597
Înainte de apelul metodei cu argumente: 987, 1597. Număr curent = 2584
Înainte de apelul metodei cu argumente: 1597, 2584. Număr curent = 4181
Înainte de metoda apel cu argumente: 2584, 4181. Număr curent = 6765
Înainte de apelul metodei cu argumente: 4181, 6765. Număr curent = 10946
Înainte de apelul cu argumente: 6765, 10946. Număr curent = 17711
Înainte de apelul cu argumente: 107716. Număr curent = 28657
Înainte de apelul metodei cu args: 17711, 28657. Număr curent = 46368
Înainte de apelul metodei cu args: 28657, 46368. Număr curent = 75025
Înainte de apelul metodei cu args: 46368, 75025. Numărul curent = 121393
args: Înainte de apelul metodei cu args: 46368, 75025. 121393. Număr curent = 196418
Înainte de Metoda Apelați cu Args: 121393, 196418. Număr curent = 317811
Înainte de Metoda Apelați cu Args: 196418, 317811. Numărul curent = 514229
Înainte de Metoda Apelați cu Args: 317811, 514229. Numărul curent = 832040
înainte de metoda Metoda : apel cu argumente: 514229, 832040. Număr curent = 1346269
Înainte de apelul metodei cu argumente: 832040, 1346269. Număr curent = 2178309
Înainte de apelul cu argument: 1346269, 2178309 = 352 Număr curent = 352
Înainte de apelul metodei cu argumente: 2178309, 3524578. Număr curent = 5702887
Înainte de apelul metodei cu argumente: 3524578, 5702887. Număr curent = 9227465
Înainte de apelul metodei cu argumente: 5702887, 9223 Înainte de apelul metodei cu argumente: 9227, 9227 args = 3 14 923
227465, 14930352. Număr curent = 24157817
Înainte de apelul metodei cu argumente: 14930352, 24157817. Număr curent = 39088169
Înainte de apelul metodei cu argumente: 24157817, 39088169. Numărul curent = 8688169 înainte de metoda
args: 868: 6345 3245986. Număr curent = 102334155
Înainte de metoda apel cu argumente: 63245986, 102334155. Număr curent = 165580141
Înainte de metoda apel cu argumente: 102334155, 165580141. Număr curent = 267914296
Înainte de apelul de metodă cu argumente: 165580141, 267914296. Număr curent = 433494437
Înainte de apelul de metodă cu argumente: 267914296, 433494437. Număr curent = 701408733 Înainte de apelul de metodă cu args: 14304747, 143047474304370437437.
34903170
Înainte de apelul metodei cu argumente: 701408733, 1134903170. Număr curent = 1836311903
După apelul metodei cu args: 701408733, 113490317 După apelul metodei cu args: 433494437,
701408733 După apelul metodei cu args: 23490317 După apelul metodei cu args: 236:7944337 165580141, 267914296 După apelul metodei cu argumente: 102334155, 165580141 După apelul metodei cu argumente: 63245986, 102334155 După apelul metodei cu argumente: 39088169, 63245986
După apelul metodei cu args: 24157817, 39088169
După apelul metodei cu args: 14930352, 24157817
După apelul metodei cu args: 9227465, 14930352 După apelul metodei cu args: 570282874, după
metoda cu args
: 5702874, args 5702887
După apelul metodei cu argumente : 2178309, 3524578
După apelul metodei cu args: 1346269, 2178309
După apelul metodei cu args: 832040, 1346269 După apelul metodei cu args
: 514229, 832040 După apelul metodei cu 15 args arg 2:1 196418, 317811 După Apelul metodei cu argumente: 121393, 196418 După apelul metodei cu argumente: 75025, 121393 După apelul metodei cu argumente: 46368, 75025
După apelul metodei cu args: 28657, 46368
După apelul metodei cu args: 17711, 28657
După apelul metodei cu args: 10946,
17711 După apelul metodei cu args: 6765, 10946
După apelul metodei cu args: 47185
după apelul metodei 6 cu args: 47185 : 2584, 4181
După apelarea metodei cu argumente: 1597, 2584
După apelarea metodei cu argumente: 987, 1597
După apelarea metodei cu argumente: 610, 987
După apelarea metodei cu argumente: 377, 610 După apelarea metodei cu argumente: 2584, 987 După apelarea metodei cu argumente: 377, 610
După apelarea metodei cu argumente: 2584,
4181 Apelul metodei cu argumente: 144, 233
După apelul metodei cu argumente: 89, 144
După apelul metodei cu argumente: 55, 89
După apelul metodei cu argumente: 34, 55
După apelul metodei cu argumente: 21, 34
După apelarea metodei cu argumente: 13, 21
După apelarea metodei cu argumente: 8, 13
După apelarea metodei cu argumente: 5, 8
După apelarea metodei cu argumente: 3, 5
După apelarea metodei cu argumente: 2, 3
După apelarea metodei cu argumente : 1, 2
După apelul metodei cu argumente: 1, 1
După apelul metodei cu argumente: 0, 1
Iată o vizualizare a ceea ce se întâmplă.
Să o spunem din nou: se numește metoda printFibonacciWithCondition . Acesta calculează numărul curent. Dacă ni se potrivește, atunci îl afișăm și apelăm din nou metoda printFibonacciWithCondition cu argumente noi.
Atâta timp cât este apelată metoda recursivă, aceasta se numește „coborâre recursivă”. Când recursiv se termină și apelurile de metodă revin, spunem că stiva de apeluri se „desface”.
Recursiunea este un subiect interesant în programare. Pentru a înțelege mai bine materialul, să ne schimbăm ușor sarcina. Noua sarcină este de a scoate, în ordine descrescătoare, toate numerele din seria Fibonacci care nu depășesc Integer.MAX_VALUE . Am scris deja tot codul necesar pentru această sarcină. Tot ce rămâne este să schimbați ordinea de afișare a numărului curent și apelarea metodei recursive. Adică, în primul exemplu, numărul calculat a fost afișat în timpul „coborârii”, dar acum trebuie să „coborâm până la fund” și apoi să afișăm numerele „pe drumul înapoi în sus”. Și bineînțeles, în metoda principală , schimbăm cele două numere inițiale ale secvenței (zero și unu) după ce le afișăm după ce numim metoda recursivă. Pentru lizibilitate,metodă.
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);
}
}
Ieșirea va fi:
1134903170
701408733 433494437 267914296 165580141
102334155 63245986 39088169 241580169 241580141 241580141 87. 233 144 89 55 34 21 13 8 5 3 2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1
1
0
GO TO FULL VERSION