Recursie in Java

1. Inleiding

In dit artikel zullen we ons concentreren op een kernconcept in elke programmeertaal: recursie.

We zullen de kenmerken van een recursieve functie en laten zien hoe u recursie kunt gebruiken om verschillende problemen in Java op te lossen.

2. Begrijp recursie

2.1. De definitie

In Java ondersteunt het functie-aanroepmechanisme de mogelijkheid om zelf een methode aan te roepen. Deze functionaliteit staat bekend als herhaling.

Stel dat we de gehele getallen van 0 tot een bepaalde waarde willen optellen n:

publieke int sum (int n) {if (n> = 1) {return sum (n - 1) + n; } terugkeer n; }

Er zijn twee hoofdvereisten voor een recursieve functie:

  • Een stopvoorwaarde - de functie retourneert een waarde wanneer aan een bepaalde voorwaarde is voldaan, zonder een verdere recursieve aanroep
  • De recursieve oproep - de functie roept zichzelf aan met een invoer wat een stap dichter bij de stopconditie is

Elke recursieve aanroep voegt een nieuw frame toe aan het stapelgeheugen van de JVM. Zo, als we er niet op letten hoe diep onze recursieve aanroep kan duiken, kan er een uitzondering optreden vanwege onvoldoende geheugen.

Dit potentiële probleem kan worden vermeden door gebruik te maken van optimalisatie van de staartrecursie.

2.2. Staartrecursie versus hoofdrecursie

We verwijzen naar een recursieve functie als staartrecursiewanneer de recursieve aanroep het laatste is dat door de functie wordt uitgevoerd. Anders staat het bekend als hoofd-recursie.

Onze implementatie hierboven van de som() functie is een voorbeeld van hoofdrecursie en kan worden gewijzigd in staartrecursie:

public int tailSum (int currentSum, int n) {if (n <= 1) {return currentSum + n; } return tailSum (currentSum + n, n - 1); }

Met staartrecursie, de recursieve aanroep is het laatste wat de methode doet, dus er is niets meer uit te voeren binnen de huidige functie.

Logischerwijs is het dus niet nodig om het stapelframe van de huidige functie op te slaan.

Hoewel de compiler kan gebruik dit punt om het geheugen te optimaliseren, moet worden opgemerkt dat de Java-compiler optimaliseert voorlopig niet voor staartrecursie.

2.3. Recursie versus herhaling

Recursie kan de implementatie van enkele gecompliceerde problemen helpen vereenvoudigen door de code duidelijker en leesbaarder te maken.

Maar zoals we al hebben gezien, vereist de recursieve benadering vaak meer geheugen, aangezien het vereiste stapelgeheugen toeneemt met elke recursieve aanroep.

Als alternatief kunnen we, als we een probleem met recursie kunnen oplossen, dit ook oplossen door iteratie.

Bijvoorbeeld onze som methode kan worden geïmplementeerd met behulp van iteratie:

public int iterativeSum (int n) {int sum = 0; if (n <0) {return -1; } for (int i = 0; i <= n; i ++) {som + = i; } retourbedrag; }

In vergelijking met recursie kan de iteratieve benadering mogelijk betere prestaties opleveren. Dat gezegd hebbende, zal iteratie ingewikkelder en moeilijker te begrijpen zijn in vergelijking met recursie, bijvoorbeeld: een binaire boom doorkruisen.

Het maken van de juiste keuze tussen koprecursie, staartrecursie en een iteratieve aanpak hangt af van het specifieke probleem en de situatie.

3. Voorbeelden

Laten we nu proberen enkele problemen op een recursieve manier op te lossen.

3.1. N-Th Power of Ten vinden

Stel dat we de n-de macht van 10. Hier is onze inbreng n. Als we recursief denken, kunnen we rekenen (n-1)-de macht van 10 eerst, en vermenigvuldig het resultaat met 10.

Om vervolgens de (n-1)-de macht van 10 zal de (n-2)-de macht van 10 en vermenigvuldig dat resultaat met 10, enzovoort. We gaan zo door totdat we op een punt komen waarop we de (n-n) -de macht van 10 moeten berekenen, wat 1 is.

Als we dit in Java zouden willen implementeren, zouden we schrijven:

public int powerOf10 (int n) {if (n == 0) {return 1; } retourneer powerOf10 (n-1) * 10; }

3.2. Het vinden van het N-de element van de Fibonacci-reeks

Beginnend met 0 en 1, de Fibonacci-reeks is een reeks getallen waarbij elk getal wordt gedefinieerd als de som van de twee cijfers die eraan komen: 0 1 1 2 3 5 8 13 21 34 55

Dus een nummer gegeven n, ons probleem is om de n-de element van Fibonacci-reeks. Om een ​​recursieve oplossing te implementeren, moeten we de Stop conditie en de Recursieve oproep.

Gelukkig is het heel eenvoudig.

Laten we bellen f (n) de n-de waarde van de reeks. Dan hebben we f (n) = f (n-1) + f (n-2) (de Recursieve oproep).

Ondertussen, f (0) = 0 en f (1) = 1 ( Stop conditie).

Dan is het voor ons heel duidelijk om een ​​recursieve methode te definiëren om het probleem op te lossen:

public int fibonacci (int n) {if (n <= 1) {return n; } retourneer fibonacci (n-1) + fibonacci (n-2); }

3.3. Omzetten van decimaal naar binair

Laten we nu eens kijken naar het probleem van het converteren van een decimaal getal naar een binair getal. De vereiste is om een ​​methode te implementeren die een positieve gehele waarde ontvangt n en retourneert een binair getal Draad vertegenwoordiging.

Een manier om een ​​decimaal getal naar een binair getal om te zetten, is door de waarde door 2 te delen, de rest op te nemen en het quotiënt door 2 te blijven delen.

We blijven zo delen totdat we een quotiënt van krijgen 0. Vervolgens, door alle restanten in reservevolgorde uit te schrijven, verkrijgen we de binaire string.

Daarom is ons probleem om een ​​methode te schrijven die deze restanten in reservevolgorde retourneert:

public String toBinary (int n) {if (n <= 1) {return String.valueOf (n); } return toBinary (n / 2) + String.valueOf (n% 2); }

3.4. Hoogte van een binaire boom

De hoogte van een binaire boom wordt gedefinieerd als het aantal randen van de wortel tot het diepste blad. Ons probleem is nu om deze waarde voor een gegeven binaire boom te berekenen.

Een eenvoudige benadering zou zijn om het diepste blad te vinden en vervolgens de randen tussen de wortel en dat blad te tellen.

Maar als we een recursieve oplossing proberen te bedenken, kunnen we de definitie voor de hoogte van een binaire boom herformuleren als de maximale hoogte van de linkertak van de wortel en de rechtertak van de wortel, plus 1.

Als de wortel geen linkertak en rechtertak heeft, is de hoogte nul.

Hier is onze implementatie:

public int berekenTreeHeight (BinaryNode root) {if (root! = null) {if (root.getLeft ()! = null || root.getRight ()! = null) {return 1 + max (berekenTreeHeight (root.left), berekenTreeHeight (root.right)); }} retourneren 0; }

Daarom zien we dat sommige problemen kunnen op een heel eenvoudige manier worden opgelost met recursie.

4. Conclusie

In deze tutorial hebben we het concept van recursie in Java geïntroduceerd en gedemonstreerd met een paar eenvoudige voorbeelden.

De implementatie van dit artikel is te vinden op Github.