streamalism.org

1. Introduktion

I denne artikel vil vi fokusere på et kernekoncept på ethvert programmeringssprog - rekursion.

Vi forklarer egenskaberne ved en rekursiv funktion og vise, hvordan man bruger rekursion til at løse forskellige problemer i Java.

2. Forstå rekursion

2.1. Definitionen

I Java understøtter funktionskaldemekanismen muligheden for at få en metode til at kalde sig selv. Denne funktionalitet kaldes rekursion.

Antag for eksempel, at vi vil summere heltalene fra 0 til en eller anden værdi n:

offentlig int-sum (int n) {if (n> = 1) {return sum (n - 1) + n; } returner n; }

Der er to hovedkrav til en rekursiv funktion:

• En standstilstand - funktionen returnerer en værdi, når en bestemt betingelse er opfyldt, uden et yderligere rekursivt opkald
• Det rekursive opkald - funktionen kalder sig selv med en input hvilket er et skridt nærmere stoptilstanden

Hvert rekursivt opkald tilføjer en ny ramme til stakhukommelsen på JVM. Så, hvis vi ikke er opmærksomme på, hvor dybt vores rekursive opkald kan dykke, kan der forekomme en undtagelse uden hukommelse.

Dette potentielle problem kan afværges ved at udnytte optimering af tail-rekursion.

2.2. Hale rekursion versus hoved rekursion

Vi henviser til en rekursiv funktion som hale-rekursionnår det rekursive opkald er det sidste, som funktionen udfører. Ellers er det kendt som hovedrekursion.

Vores implementering ovenfor af sum() funktion er et eksempel på hovedrekursion og kan ændres til halerekursion:

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

Med hale rekursion, det rekursive opkald er det sidste, metoden gør, så der er intet tilbage at udføre inden for den aktuelle funktion.

Logisk er der således ikke behov for at gemme den aktuelle funktions stakramme.

Selvom kompilatoren kan bruge dette punkt til at optimere hukommelse, skal det bemærkes, at Java-kompilator optimerer ikke til hale-rekursion for nu.

2.3. Rekursion versus gentagelse

Rekursion kan hjælpe med at forenkle implementeringen af ​​nogle komplicerede problemer ved at gøre koden klarere og mere læselig.

Men som vi allerede har set, kræver den rekursive tilgang ofte mere hukommelse, da den krævede stackhukommelse stiger med hvert rekursive opkald.

Som et alternativ, hvis vi kan løse et problem med rekursion, kan vi også løse det ved iteration.

For eksempel vores sum metoden kunne implementeres ved hjælp af iteration:

public int iterativeSum (int n) {int sum = 0; hvis (n <0) {return -1; } for (int i = 0; i <= n; i ++) {sum + = i; } returneringssum }

Sammenlignet med rekursion kan den iterative tilgang muligvis give bedre ydeevne. Når det er sagt, vil iteration være mere kompliceret og sværere at forstå sammenlignet med rekursion, for eksempel: at krydse et binært træ.

At træffe det rigtige valg mellem hovedrekursion, halenrekursion og en iterativ tilgang afhænger alt af det specifikke problem og situation.

3. Eksempler

Lad os nu prøve at løse nogle problemer på en rekursiv måde.

3.1. Find N-Th Power of Ten

Antag, at vi skal beregne n-th styrke på 10. Her er vores input n. Når vi tænker på en rekursiv måde, kan vi beregne (n-1)-te styrke på 10 først, og gang resultatet med 10.

Derefter for at beregne (n-1)-th magt på 10 vil være (n-2)-th effekt på 10 og gang dette resultat med 10 og så videre. Vi fortsætter sådan, indtil vi kommer til et punkt, hvor vi har brug for at beregne (n-n) -th effekt på 10, som er 1.

Hvis vi ville implementere dette i Java, ville vi skrive:

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

3.2. Find N-Th Element of Fibonacci Sequence

Begyndende med 0 og 1, det Fibonacci-sekvens er en række af tal, hvor hvert nummer er defineret som summen af ​​de to tal, der fortsætter det: 0 1 1 2 3 5 8 13 21 34 55 …

Så givet et nummer n, vores problem er at finde n-th element af Fibonacci-sekvens. For at implementere en rekursiv løsning skal vi finde ud af Stop tilstand og Rekursivt opkald.

Heldigvis er det virkelig ligetil.

Lad os ringe f (n) det n-te værdi af sekvensen. Så får vi det f (n) = f (n-1) + f (n-2) (det Rekursivt opkald).

I mellemtiden f (0) = 0 og f (1) = 1 ( Stop tilstand).

Derefter er det virkelig indlysende for os at definere en rekursiv metode til at løse problemet:

public int retracement (int n) {if (n <= 1) {return n; } returnere Fibonacci (n-1) + Fibonacci (n-2); }

3.3. Konvertering fra decimal til binær

Lad os nu overveje problemet med at konvertere et decimaltal til binært. Kravet er at implementere en metode, der modtager en positiv heltal n og returnerer en binær Snor repræsentation.

En tilgang til at konvertere et decimaltal til binært er at dele værdien med 2, registrere resten og fortsætte med at dividere kvotienten med 2.

Vi bliver ved med at dele sådan, indtil vi får et kvotient på 0. Derefter får vi den binære streng ved at skrive alle resterne ud i reserve rækkefølge.

Derfor er vores problem at skrive en metode, der returnerer disse resterende i reserve rækkefølge:

public String toBinary (int n) {if (n <= 1) {return String.valueOf (n); } vende tilbage til Binær (n / 2) + String.valueOf (n% 2); }

3.4. Højde af et binært træ

Højden på et binært træ defineres som antallet af kanter fra roden til det dybeste blad. Vores problem er nu at beregne denne værdi for et givet binært træ.

En enkel tilgang ville være at finde det dybeste blad og derefter tælle kanterne mellem roden og bladet.

Men når vi prøver at tænke på en rekursiv løsning, kan vi gentage definitionen for højden af ​​et binært træ som den maksimale højde af rodens venstre gren og rodens højre gren plus 1.

Hvis roden ikke har nogen venstre gren og højre gren, er dens højde nul.

Her er vores implementering:

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

Derfor ser vi det nogle problemer kan løses med rekursion på en virkelig enkel måde.

4. Konklusion

I denne vejledning har vi introduceret begrebet rekursion i Java og demonstreret det med et par enkle eksempler.

Implementeringen af ​​denne artikel kan findes på Github.