Voorbeeld van recursieve code zonder exit-voorwaarde
Laten we nog eens kijken naar een recursief probleem. Overweeg bijvoorbeeld om Fibonacci-getallen te berekenen. Iedereen zal zich herinneren dat de Fibonacci-reeks een numerieke reeks is waarin de eerste twee getallen 0 en 1 zijn, en elk volgend getal is gelijk aan de som van de twee voorgaande getallen.
Laten we code schrijven om deze getallen te berekenen en weer te geven:
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);
}
}
Druk vóór de eerste aanroep van de recursieve printFibonacci -methode de eerste twee getallen van de reeks af: nul en één. We moeten dit doen omdat de recursieve methode alleen de som van de invoerparameters weergeeft, niet de parameters zelf.
De code ziet er goed uit: we krijgen twee getallen, berekenen hun som, drukken het af op de console en roepen de printFibonacci -methode opnieuw recursief aan. We geven het vorige nummer (vorige) en het huidige nummer (current) door als argumenten.
Eigenlijk bevat de code twee fouten. Je kunt ze zien als je de code uitvoert.
De eerste fout is het overlopen van het lange type. Het 104e getal in onze reeks is negatief, wat aangeeft dat het lange type overstroomde.
De tweede fout is anders. Na het berekenen van ongeveer 12.000 getallen krijgen we:
Dit is een geschikt moment om te onthouden wat een methodeaanroepstack is in Java. De Java-machine houdt alle functieaanroepen bij. Om dit te doen, gebruikt het een speciaal soort verzameling, een stapel genaamd. Wanneer een functie een andere aanroept, duwt de Java-machine een nieuw StackTraceElement op de stapel. Wanneer de functie eindigt, wordt dit element van de stapel verwijderd. Dienovereenkomstig slaat de stapel altijd up-to-date informatie op over de huidige status van de functieaanroepstapel. De documentatie voor StackTraceElement zegt dat het wordt "gegooid wanneer een stackoverloop optreedt omdat een toepassing te diep terugkeert." Een draaiende JVM heeft een speciaal geheugengebied voor het opslaan van de method call stack. De grootte van dit geheugengebied is afhankelijk van de OS- en JVM-instellingen. Naast de methodeaanroepstack zelf, primitieve variabelen (specifieke waarden van methodeparameters) en de adressen van referentievariabelen (in een geheugengebied genaamd de "heap") worden opgeslagen in dit speciale geheugengebied. Toegang tot de call-stack volgt het LIFO-principe.
Gecorrigeerd voorbeeld met een exit-voorwaarde
Laten we beginnen met het oplossen van het tweede probleem in de code.
Laten we proberen het probleem frontaal op te lossen: als de stapel te klein is, laten we hem dan groter maken. Om dit te doen, start u de JVM met de vlag "-Xss" en geeft u op hoeveel geheugen u wilt toewijzen aan de stapel. Laten we proberen 5 megabyte toe te wijzen. Zo ziet het eruit in IDEA:
We zijn erin geslaagd om de lengte van de uitvoer te vergroten. Kan nu meer dan 49.000 nummers van de reeks berekenen in plaats van beperkt te zijn tot ongeveer 12.000 nummers. Maar op een gegeven moment krijgen we nog steeds een StackOverflowError .
Je kunt proberen de stapel te vergroten, maar dat lost het fundamentele probleem niet op. Laten we dus eens kijken naar een probleem in de logica. Er moet een punt zijn waarop de recursie stopt. Met andere woorden, er moet een voorwaarde zijn die bepaalt wanneer de recursieve methode niet langer wordt aangeroepen, waardoor de call-stack kan ontspannen. Om een dergelijke voorwaarde te definiëren, laten we ons doel expliciet maken: de Fibonacci-reeks weergeven zolang de getallen kleiner zijn dan Integer.MAX_VALUE .
Laten we een nieuwe printFibonacciWithCondition -methode schrijven die rekening houdt met deze voorwaarde. En we zullen de nieuwe gecorrigeerde methode in de hoofdmethode noemen.
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);
}
}
Na het uitvoeren van de code zien we dat de uitvoer eindigt met het getal 1836311903. Het getal ervoor is 1134903170. De som van deze getallen is 2_971_215_073, wat inderdaad groter is dan Integer.MAX_VALUE (2_147_483_647 ) .
Deze wijziging loste automatisch de lange overflow-bug op. Als u meer van de reeksen moet berekenen, moet u andere gegevenstypen gebruiken, zoals BigInteger .
Recursieve afdaling en ontspanning
Laten we stap voor stap analyseren hoe onze code wordt uitgevoerd. Om dit te doen, voegen we een echo -methode toe en roepen deze aan voor en na de recursieve aanroep van de printFibonacciWithCondition -methode.
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);
}
}
}
Het programma geeft ons deze output:
1
Voor methodeaanroep met args: 0, 1. Huidig getal = 1
Voor methodeaanroep met args: 1, 1. Huidig getal = 2
Voor methodeaanroep met args: 1, 2. Huidig getal = 3
Voor methodeaanroep met args: 2, 3. Huidig nummer = 5
Voor methodeaanroep met args: 3, 5. Huidig nummer = 8
Voor methodeaanroep met args: 5, 8. Huidig nummer = 13
Voor methodeaanroep met args: 8, 13. Huidig nummer = 21
Voor methodeaanroep met args: 13, 21. Huidig nummer = 34
Voor methodeaanroep met args: 21, 34. Huidig nummer = 55
Voor methodeaanroep met args: 34, 55. Huidig getal = 89
Voor methodeaanroep met args: 55, 89. Huidig aantal = 144
Voor methodeaanroep met args: 89, 144. Huidig nummer = 233
Voor methodeaanroep met args: 144, 233. Huidig nummer = 377
Voor methodeaanroep met args: 233, 377. Huidig nummer = 610
Voor methodeaanroep met args: 377, 610. Huidig nummer = 987
Voor methodeaanroep met args: 610, 987. Huidig nummer = 1597
Voor methodeaanroep met args: 987, 1597. Huidig nummer = 2584
Voor methodeaanroep met args: 1597, 2584. Huidig nummer = 4181
Voor methode call met args: 2584, 4181. Huidig nummer = 6765
Before method call met args: 4181, 6765. Huidig nummer = 10946
Before method call met args: 6765, 10946. Huidig nummer = 17711
Before method call met args: 10946, 17711. Huidig nummer = 28657
Voor aanroep methode met args: 17711, 28657. Huidig nummer = 46368
Voor aanroep methode met args: 28657, 46368. Huidig nummer = 75025
Voor aanroep methode met args: 46368, 75025. Huidig nummer = 121393
Voor aanroep methode met args: 75025, 121393. Huidig nummer = 196418
vóór de methode Call met args: 121393, 196418. Huidig nummer = 317811
vóór methode Call met args: 196418, 317811. Huidig nummer = 514229
Voor methode Call met args: 317811,
514229 aanroep met args: 514229, 832040. Huidig nummer = 1346269
Aanroep voor methode met args: 832040, 1346269. Huidig nummer = 2178309
Aanroep voor methode met args: 1346269, 2178309. Huidig nummer = 3524578
Voor methodeaanroep met args: 2178309, 3524578. Huidig nummer = 5702887
Voor methodeaanroep met args: 3524578, 5702887. Huidig nummer = 9227465
Voor methodeaanroep met args: 5702887, 9227465. Huidig nummer = 14930352
Voor methodeaanroep met args: 9 227465, 14930352. Huidig nummer = 24157817
Vóór methodeaanroep met args: 14930352, 24157817. Huidig nummer = 39088169
Vóór methodeaanroep met args: 24157817, 39088169. Huidig nummer = 63245986 Vóór methodeaanroep met args: 39088169
, 6 3245986. Huidig nummer = 102334155
Vóór methode bel met args: 63245986, 102334155. Huidig nummer = 165580141
Vóór methode bel met args: 102334155, 165580141. Huidig nummer = 267914296
Voor methodeaanroep met args: 165580141, 267914296. Huidig nummer = 433494437
Voor methodeaanroep met args: 267914296, 433494437. Huidig nummer = 701408733 Voor
methodeaanroep met args: 433494437, 701408733. Huidig nummer = 11 34903170
Vóór methodeaanroep met args: 701408733, 1134903170. Huidig nummer = 1836311903
Na methodeaanroep met args: 701408733, 113490317
Na methodeaanroep met args: 433494437, 701408733 Na methodeaanroep met args: 267914296, 433494437 Na
methodeaanroep
met args: 165580141, 267914296
Na methodeaanroep met args: 102334155, 165580141
Na methodeaanroep met args: 63245986, 102334155
Na methodeaanroep met args: 39088169, 63245986
Na methodeaanroep met args: 24157817, 39088169
Na methodeaanroep met args: 14930352, 24157817 Na
methodeaanroep met args: 9227465, 14930352 Na methodeaanroep met args: 5702887, 9227465 Na methodeaanroep met args: 3524578, 5702887
Na methodeaanroep met args : 2178309, 3524578 Na methodeaanroep met args: 1346269, 2178309 Na methodeaanroep met args: 832040, 1346269 Na methodeaanroep met args: 514229, 832040 Na methodeaanroep met args: 317811 , 514229 Na methodeaanroep met args: 196418, 317811 daarna methodeaanroep met args: 121393, 196418 Na methodeaanroep met args: 75025, 121393 Na methodeaanroep met args: 46368, 75025
Na methodeaanroep met args: 28657, 46368
Na methodeaanroep met args: 17711, 28657
Na methodeaanroep met args: 10946, 17711
Na methodeaanroep met args: 6765, 10946 Na methodeaanroep met
args: 4181, 6765
Na methodeaanroep met args : 2584, 4181
Na methodeaanroep met args: 1597, 2584
Na methodeaanroep met args: 987, 1597
Na methodeaanroep met args: 610, 987
Na methodeaanroep met args: 377, 610
Na methodeaanroep met args: 233, 377
Na methodeaanroep met args: 144, 233
Na methodeaanroep met args: 89, 144
Na methodeaanroep met args: 55, 89
Na methodeaanroep met args: 34, 55
Na methodeaanroep met args: 21, 34
Na methodeaanroep met args: 13, 21
Na methodeaanroep met args: 8, 13
Na methodeaanroep met args: 5, 8
Na methodeaanroep met args: 3, 5 Na methodeaanroep
met args: 2, 3
Na methodeaanroep met args : 1, 2
Na methodeaanroep met argumenten: 1, 1
Na methodeaanroep met argumenten: 0, 1
Hier is een visualisatie van wat er gebeurt.
Laten we het nog een keer zeggen: de methode printFibonacciWithCondition wordt aangeroepen. Het berekent het huidige aantal. Als het ons uitkomt, geven we het weer en roepen we de methode printFibonacciWithCondition opnieuw aan met nieuwe argumenten.
Zolang de recursieve methode wordt aangeroepen, wordt dit "recursieve afdaling" genoemd. Wanneer recursief eindigt en methode-aanroepen terugkeren, zeggen we dat de call-stack aan het "afwikkelen" is.
Recursie is een interessant onderwerp in programmeren. Laten we onze taak een beetje veranderen om het materiaal beter onder de knie te krijgen. De nieuwe taak is om in aflopende volgorde alle getallen in de Fibonacci-reeks uit te voeren die niet groter zijn dan Integer.MAX_VALUE . We hebben al alle code geschreven die nodig is voor deze taak. Het enige dat overblijft is om de volgorde van het weergeven van het huidige nummer en het aanroepen van de recursieve methode om te wisselen. Dat wil zeggen, in het eerste voorbeeld werd het berekende aantal weergegeven tijdens de "afdaling", maar nu moeten we "helemaal naar beneden afdalen" en vervolgens nummers weergeven "op de terugweg naar boven". En natuurlijk wisselen we in de hoofdmethode de twee beginnummers van de reeks (nul en één) om nadat we ze hebben weergegeven nadat we de recursieve methode hebben aangeroepen. Voor de leesbaarheid,methode.
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);
}
}
De uitvoer zal zijn:
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