Introduksjon til rekursiv funksjon i Java
En rekursiv funksjon er den som kaller seg en eller mange ganger. En rekursiv funksjon brukes i situasjoner der det samme settet med operasjoner må utføres igjen og igjen til resultatet er nådd. Den utfører flere iterasjoner, og problemstillingen blir stadig enklere med hver iterasjon.
Det må alltid spesifiseres en basisgrense når du skriver en rekursiv funksjon ellers resulterer det i Stack Overflow-feil. En stabel er et minneområde som er reservert for å opprettholde metodeinnkallinger. Feilen skyldes at funksjonen begynner å eksekveres kontinuerlig, da den ikke vil være i stand til å finne den begrensende tilstanden og dermed til slutt utmatte det tildelte minnet. Så for å forhindre Stack Overflow definerer vi visse baseforhold ved hjelp av "if … else" -utsagn (eller andre betingede utsagn) som gjør at rekursjonsfunksjonen stopper så snart den nødvendige beregningen er fullført.
Rekursjonstyper i Java
Det er to typer rekursjon i Java. De er:
1. Direkte rekursjon
syntaks:
Her kaller funksjonen seg kontinuerlig, og er derfor en rekursiv funksjon.
public static void main(String() args)(
//few lines of code
function();
//few lines of code
)
function() (
//few lines of code
function();
//few lines of code
)
Eksempel
Factorial av et nummer er et eksempel på direkte rekursjon. Grunnprinsippet for rekursjon er å løse et komplekst problem ved å dele opp i mindre. For eksempel ved faktorering av et tall beregner vi faktoriet til "i" hvis vi vet dets faktoriale til "i-1".
Kode:
public class Factorial (
static int fact(int i)(
if (i == 1)
return 1;
else
return(i * fact(i-1));
)
public static void main(String() args) (
System.out.println("The factorial of given number 6 is: "+fact(6));
)
)
Produksjon:
2. Indirekte / gjensidig rekursjon
En funksjon1 som kaller en annen funksjon2, som i sin tur kaller funksjon1 enten direkte eller indirekte kalles en indirekte rekursiv funksjon.
syntaks:
Vurder 2 funksjoner kalt funksjon1 () og funksjon2 (). Her kaller funksjon1 funksjon2 og funksjon2 samtaler funksjon1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Eksempel
For å vise indirekte rekursjon tar vi følgende program som brukes for å finne ut om et gitt antall er jevnt eller rart fra den gitte inngangen.
Kode:
import java.util.Scanner;
public class IndirectRecursion (
public static boolean oddNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return false;
) else (
return evenNum(i-1);
)
)
public static boolean evenNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return true;
) else (
return oddNum(i-1);
)
)
public static void main(String() args) (
Scanner inputNum = new Scanner(System.in);
System.out.print("Give a number: ");
int n = inputNum.nextInt();
if (evenNum(n)) System.out.println(n + " is even");
else System.out.println(n + " is odd");
inputNum.close();
)
)
Produksjon:
Eksempler på rekursjon i Java
Her er noen flere eksempler for å løse problemene ved hjelp av rekursjonsmetoden.
Eksempel 1 - Fibonacci-sekvens
Et sett med "n" tall sies å være i en Fibonacci-sekvens hvis nummer3 = tall1 + tall2, dvs. at hvert tall er en sum av de foregående to tallene. Følgelig starter sekvensen alltid med de to første sifrene som 0 og 1. Det tredje sifferet er en sum av 0 og 1 som resulterer i 1, det fjerde tallet er tillegg av 1 og 1 som resulterer i 2, og sekvensen fortsetter.
Sjekk ut følgende kode i Java for å generere en Fibonacci-sekvens:
public class FibonacciSeries(
static int num1=0, num2=1, num3=0;
static void fibonacci(int n)(
if(n>0)(
num3 = num1 + num2;
num1 = num2;
num2 = num3;
System.out.print(" "+num3);
fibonacci(n-1);
)
)
public static void main(String args())(
int n=10;
System.out.print(num1+" "+num2);//printing constant first two digits 0 and 1
fibonacci(n-2);//Since first two numbers are already done
)
)
Produksjon:
Her initialiseres de to første numrene til 0 og 1 og skrives ut. Variablene “num1”, “num2” og “num3” brukes til å generere den nødvendige sekvensen. Variabel “num3” fås ved å legge til “num1” og “num2” og tallene forskyves en plassering til venstre ved å blande som vist i koden. Funksjonen “Fibonacci” kalles rekursivt her, og ved hver iterasjon reduseres verdien av “n” med 1. Derfor rekursjonen kommer ut så snart “n” når verdien 0.
Eksempel 2 - Tower Of Hanoi
Dette er et klassisk matematisk problem som har 3 poler og "n" antall disker med forskjellige størrelser. Puslespillet går som følger:
I begynnelsen vil den første polen ha skivene ordnet slik at den største platen av dem alle er i bunnen og den minste på toppen av stolpen. Målet er å flytte disse skivene fra den første polen til den tredje polen og holde skivene i samme posisjon som i den første. Følgende er noen forhold du må huske på når du skifter disse diskene:
1. Om gangen må bare en disk flyttes.
2. I prosessen er det ikke tillatt å plassere en større disk over en mindre.
3. Den andre (midtre) polen kan brukes til å megle mens du overfører platene fra første til andre pol.
Følgende er Java-koden som kan brukes til å løse puslespillet:
Kode:
public class TowerOfHanoi (
public static void main(String() args) (
int count = 3;
tower(count, 'A', 'B', 'C');
)
public static void tower(int first, char disk1, char temp, char disk2) (
if (first == 1) (
System.out.println("Disk 1 from " + disk1 + " to " + disk2);
) else (
tower(first - 1, disk1, disk2, temp);
System.out.println("Disk " + first + " from " + disk1 + " to " + disk2);
tower(first - 1, temp, disk1, disk2);
)
)
)
Produksjon:
Her representerer variabelen "count" antall plater som skal brukes. Funksjonen "tårn" er den rekursive funksjonen som brukes til å flytte skivene fra stang 1 til stang 3. En enkel løsning på dette problemet kan tilbys ved å vurdere to plater med det første.
- Først starter vi med å flytte skive1 fra stang 1 til stang 2.
- Deretter flytter vi plate 2 til stang 3.
- Til slutt avslutter vi med å flytte plate1 til stang 3 og fullføre den nødvendige løsningen.
Det samme prinsippet blir brukt for “n” antall plater ved å flytte (n-1) platen fra stang 1 til 2 og følge lignende trinn som ovenfor.
Fordeler med rekursjon i Java
- Koden er enkel å skrive og vedlikeholde.
- Den beste metoden for å finne resultatene der det kreves et stort antall iterasjoner.
Ulemper med rekursjon i Java
- Rekursive funksjoner bruker mer minne. Dette er fordi hver gang en rekursiv funksjon kalles; minnetildeling er utført nylig for variablene på stabelen. Og den respektive minnetildelingen frigjøres så snart de variable verdiene er returnert.
- Denne prosessen med minnetildeling tar mer tid, og derfor blir utførelsen vanligvis treg.
Konklusjon
Rekursive funksjoner er relativt enklere å kode, men de er heller ikke så effektive sammenlignet med de andre eksisterende metodene. Derfor blir de hovedsakelig brukt i tilfeller der tiden som er gitt for utvikling er mindre, og også hvor et betydelig mønster kan observeres i problemet.
Anbefalte artikler
Dette er en guide til rekursjon i Java. Her diskuterer vi typene rekursjon i Java sammen med dens forskjellige eksempler med fordeler og ulemper. Du kan også se på følgende artikler for å lære mer-
- JScrollPane i Java
- Matematiske funksjoner i Java
- Matematiske funksjoner i Java
- Konstruktør i Java
- Rekursiv funksjon i Python
- Factorial-program i JavaScript