Rekursjon i Java

1. Introduksjon

I denne artikkelen vil vi fokusere på et kjernekonsept i ethvert programmeringsspråk - rekursjon.

Vi forklarer egenskapene til en rekursiv funksjon og vise hvordan du bruker rekursjon for å løse ulike problemer i Java.

2. Forstå rekursjon

2.1. Definisjonen

I Java støtter funksjonsanropsmekanismen muligheten for å få en metode til å kalle seg selv. Denne funksjonaliteten er kjent som rekursjon.

Anta for eksempel at vi vil summere heltallene fra 0 til en eller annen verdi n:

offentlig int-sum (int n) {if (n> = 1) {retur sum (n - 1) + n; } returnere n; }

Det er to hovedkrav til en rekursiv funksjon:

  • En stopptilstand - funksjonen returnerer en verdi når en viss tilstand er oppfylt, uten ytterligere rekursivt anrop
  • Den rekursive samtalen - funksjonen kaller seg med en inngang som er et skritt nærmere stopptilstanden

Hver rekursive samtale vil legge til en ny ramme i stackminnet til JVM. Så, hvis vi ikke tar hensyn til hvor dypt det rekursive anropet vårt kan dykke, kan det oppstå et unntak uten minne.

Dette potensielle problemet kan avverges ved å utnytte optimering av halen-rekursjon.

2.2. Tail Recursion Versus Head Recursion

Vi viser til en rekursiv funksjon som hale-rekursjonnår det rekursive anropet er det siste som funksjonen utfører. Ellers er det kjent som hode-rekursjon.

Vår implementering ovenfor av sum() funksjon er et eksempel på hodet rekursjon og kan endres til halen rekursjon:

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

Med hale rekursjon, det rekursive anropet er det siste metoden gjør, så det er ingenting igjen å utføre innenfor den nåværende funksjonen.

Dermed er det logisk sett ikke behov for å lagre gjeldende funksjons stabelramme.

Selv om kompilatoren kan bruke dette punktet for å optimalisere minne, bør det bemerkes at Java-kompilator optimaliserer ikke for hale-rekursjon for nå.

2.3. Rekursjon mot Iterasjon

Rekursjon kan bidra til å forenkle implementeringen av noen kompliserte problemer ved å gjøre koden tydeligere og mer lesbar.

Men som vi allerede har sett, krever den rekursive tilnærmingen ofte mer minne ettersom det nødvendige stackminnet øker for hvert rekursive anrop.

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

For eksempel vår sum metoden kan implementeres ved hjelp av iterasjon:

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

Sammenlignet med rekursjon kan den iterative tilnærmingen potensielt gi bedre ytelse. Når det er sagt, vil iterasjon være mer komplisert og vanskeligere å forstå sammenlignet med rekursjon, for eksempel: å krysse et binært tre.

Å ta det riktige valget mellom hodet rekursjon, halen rekursjon og en iterativ tilnærming avhenger alt av det spesifikke problemet og situasjonen.

3. Eksempler

La oss nå prøve å løse noen problemer på en rekursiv måte.

3.1. Å finne N-Th Power of Ten

Anta at vi må beregne n-th kraft på 10. Her er våre innspill n. Tenker på en rekursiv måte, kan vi beregne (n-1)-th kraft på 10 først, og multipliser resultatet med 10.

For å beregne (n-1)-th kraft på 10 vil være (n-2)-th kraft på 10 og multipliser resultatet med 10, og så videre. Vi fortsetter slik til vi kommer til et punkt der vi må beregne (n-n) -te kraften på 10, som er 1.

Hvis vi ønsket å implementere dette i Java, ville vi skrive:

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

3.2. Finne N-Th Element of Fibonacci Sequence

Starter med 0 og 1, de Fibonacci-sekvens er en sekvens av tall der hvert tall er definert som summen av de to tallene som fortsetter det: 0 1 1 2 3 5 8 13 21 34 55

Så gitt et tall n, vårt problem er å finne n-te element av Fibonacci-sekvens. For å implementere en rekursiv løsning, må vi finne ut Stopp tilstand og Rekursiv samtale.

Heldigvis er det veldig greit.

La oss ringe f (n) de n-te verdi av sekvensen. Så får vi f (n) = f (n-1) + f (n-2) (de Rekursiv samtale).

I mellomtiden, f (0) = 0 og f (1) = 1 ( Stopp tilstand).

Da er det veldig åpenbart for oss å definere en rekursiv metode for å løse problemet:

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

3.3. Konvertering fra desimal til binær

La oss nå vurdere problemet med å konvertere et desimaltall til binært. Kravet er å implementere en metode som mottar en positiv heltallverdi n og returnerer en binær String representasjon.

En tilnærming til å konvertere et desimaltall til binært er å dele verdien med 2, registrere resten og fortsette å dele kvotienten med 2.

Vi fortsetter å dele slik til vi får et kvotient på 0. Deretter får vi binærstrengen ved å skrive ut alle restene i reserve rekkefølge.

Derfor er problemet vårt å skrive en metode som returnerer disse restene i reserve rekkefølge:

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

3.4. Høyden på et binært tre

Høyden på et binært tre er definert som antall kanter fra roten til det dypeste bladet. Problemet vårt er nå å beregne denne verdien for et gitt binært tre.

En enkel tilnærming ville være å finne det dypeste bladet og deretter telle kantene mellom roten og det bladet.

Men når vi prøver å tenke på en rekursiv løsning, kan vi gjenta definisjonen for høyden på et binært tre som maks høyde på rotens venstre gren og rotens høyre gren, pluss 1.

Hvis roten ikke har noen venstre gren og høyre gren, er høyden null.

Her er implementeringen vår:

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

Derfor ser vi det noen problemer kan løses med rekursjon på en veldig enkel måte.

4. Konklusjon

I denne veiledningen har vi introdusert begrepet rekursjon i Java og demonstrert det med noen få enkle eksempler.

Implementeringen av denne artikkelen finner du på Github.


$config[zx-auto] not found$config[zx-overlay] not found