Introduktion til rekursiv funktion i Java
En rekursiv funktion er den, der kalder sig selv en eller mange gange. En rekursiv funktion bruges i situationer, hvor det samme sæt af operationer skal udføres igen og igen, indtil resultatet er nået. Den udfører flere iterationer, og problemopgørelsen bliver ved med at blive enklere med hver iteration.
Der skal altid specificeres en basisgrænse, mens du skriver en rekursiv funktion, ellers resulterer det i Stack Overflow-fejl. En stak er et hukommelsesområde, der er reserveret til at opretholde metodeankaldelser. Fejlen skyldes, at funktionen begynder at udføres kontinuerligt, da den ikke vil være i stand til at finde den begrænsende tilstand og dermed til sidst udtømme den tildelte hukommelse. Så for at forhindre Stack Overflow definerer vi bestemte basisbetingelser ved hjælp af ”if… else” -angivelser (eller andre betingede udsagn), der får rekursionsfunktionen til at stoppe, så snart den krævede beregning er afsluttet.
Rekursionstyper i Java
Der er 2 typer rekursion i Java. De er:
1. Direkte rekursion
Syntaks:
Her kalder funktionen sig selv kontinuerligt og er derfor en rekursiv funktion.
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 af et tal er et eksempel på direkte rekursion. Det grundlæggende princip for rekursion er at løse et komplekst problem ved at opdeles i mindre. For eksempel beregner vi faktabladet for "i" i tilfælde af faktorial af et tal, hvis vi kender dets faktoriale for "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));
)
)
Produktion:
2. Indirekte / gensidig rekursion
En funktion1, der kalder en anden funktion2, der igen kalder funktion1 enten direkte eller indirekte kaldes en indirekte rekursiv funktion.
Syntaks:
Overvej 2 funktioner kaldet funktion1 () og funktion2 (). Her kalder funktion1 funktion2 og funktion2 kalder funktion1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Eksempel
For at vise indirekte rekursion tager vi følgende program, der bruges til at finde ud af, om et givet antal er lige eller ulige fra det givne input.
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();
)
)
Produktion:
Eksempler på rekursion i Java
Her er nogle flere eksempler til at løse problemerne ved hjælp af rekursionsmetoden.
Eksempel nr. 1 - Fibonacci-sekvens
Et sæt af "n" tal siges at være i en Fibonacci-sekvens, hvis nummer3 = nummer1 + tal2, dvs. hvert tal er en sum af dets foregående to tal. Derfor starter sekvensen altid med de første to cifre som 0 og 1. Det tredje ciffer er en sum af 0 og 1, hvilket resulterer i 1, det fjerde tal er tilføjelsen af 1 og 1, der resulterer i 2, og sekvensen fortsætter.
Tjek følgende kode i Java for at 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
)
)
Produktion:
Her initialiseres de to første numre til 0 og 1 og udskrives. Variablerne “num1”, “num2” og “num3” bruges til at generere den krævede sekvens. Variabel “num3” fås ved at tilføje “num1” og “num2”, og numrene forskydes en position til venstre ved at blande som vist i koden. Funktionen "Fibonacci" kaldes rekursivt her, og ved hver iteration reduceres værdien af "n" med 1. Derfor rekursionen afslutter, så snart "n" når værdien 0.
Eksempel 2 - Tower of Hanoi
Dette er et klassisk matematisk problem, der har 3 poler og “n” antal diske med forskellige størrelser. Puslespillet går som følger:
I begyndelsen vil den første pol have skiverne arrangeret således, at den største skive af dem alle er i bunden og den mindste på toppen af stangen. Målet er at flytte disse diske fra den første pol til den tredje pol og holde skiverne i samme position som i den første. Følgende er et par forhold, som du skal huske på, mens du skifter disse diske:
1. På et tidspunkt skal der kun flyttes en disk.
2. I processen er det ikke tilladt at placere en større disk over en mindre.
3. Den anden (midterste) pol kan bruges til at formidle, mens skiverne overføres fra første til anden pol.
Følgende er Java-koden, der kan bruges til at 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);
)
)
)
Produktion:
Her repræsenterer variablen "count" antallet af diske, der skal bruges. Funktionen ”tårn” er den rekursive funktion, der bruges til at flytte skiverne fra stang 1 til stang 3. En simpel løsning på dette problem kan tilvejebringes ved at overveje 2 diske i starten.
- Først starter vi med at flytte skive1 fra stang 1 til stang 2.
- Derefter flytter vi disc2 til stang 3.
- Endelig afslutter vi med at flytte disk1 til stang 3 og færdiggøre den krævede løsning.
Samme princip anvendes for “n” antallet af diske ved at flytte (n-1) disken fra stang 1 til 2 og følge lignende trin som ovenfor.
Fordele ved rekursion i Java
- Koden er let at skrive og vedligeholde.
- Den bedste metode til at finde de resultater, hvor der kræves et stort antal iterationer.
Ulemper ved rekursion i Java
- Rekursive funktioner bruger mere hukommelse. Dette skyldes, at hver gang en rekursiv funktion kaldes; hukommelsesallokering udføres for nylig for variablerne på stakken. Og den respektive hukommelsesallokering frigøres, så snart de variable værdier returneres.
- Denne proces med hukommelsesallokering tager mere tid, og derfor er udførelsen normalt langsom.
Konklusion
Rekursive funktioner er relativt enkle at kode, men de er heller ikke så effektive sammenlignet med de andre eksisterende metoder. Derfor bruges de hovedsageligt i tilfælde, hvor tiden til udvikling er mindre, og også hvor der kan observeres et betydeligt mønster i problemet.
Anbefalede artikler
Dette er en guide til rekursion i Java. Her diskuterer vi typer af rekursion i Java sammen med dens forskellige eksempler med fordele og ulemper. Du kan også se på de følgende artikler for at lære mere-
- JScrollPane i Java
- Matematiske funktioner i Java
- Matematiske funktioner i Java
- Konstruktør i Java
- Rekursiv funktion i Python
- Factorial-program i JavaScript