Inleiding tot recursieve functie in Java
Een recursieve functie is degene die zichzelf een of meerdere keren noemt. Een recursieve functie wordt gebruikt in situaties waarin dezelfde reeks bewerkingen steeds opnieuw moet worden uitgevoerd totdat het resultaat is bereikt. Het voert verschillende iteraties uit en de probleemstelling wordt steeds eenvoudiger met elke iteratie.
Bij het schrijven van een recursieve functie moet altijd een basislimiet worden opgegeven, anders resulteert dit in Stack Overflow-fout. Een stapel is een geheugengebied gereserveerd voor het behouden van methodeaanroepen. De fout is omdat de functie continu wordt uitgevoerd omdat deze de beperkende toestand niet kan vinden en dus uiteindelijk het toegewezen geheugen kan uitputten. Dus om Stack Overflow te voorkomen, definiëren we bepaalde basisvoorwaarden met behulp van "if … else" -instructies (of andere voorwaardelijke statements) waardoor de recursiefunctie stopt zodra de vereiste berekening is voltooid.
Soorten recursie in Java
Er zijn 2 soorten recursies in Java. Zij zijn:
1. Directe recursie
Syntaxis:
Hier noemt de functie1 zichzelf continu vandaar dat het een recursieve functie is.
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
)
Voorbeeld
De factor van een getal is een voorbeeld van directe recursie. Het basisprincipe van recursie is het oplossen van een complex probleem door het op te splitsen in kleinere. In het geval van een faculteit van een getal berekenen we bijvoorbeeld de faculteit van "i" als we de faculteit van "i-1" kennen.
Code:
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));
)
)
Output:
2. Indirecte / wederzijdse recursie
Een functie1 die een andere functie2 aanroept, die op zijn beurt functie1 direct of indirect aanroept, wordt een indirecte recursieve functie genoemd.
Syntaxis:
Overweeg 2 functies genaamd function1 () en function2 (). Hier roept functie1 functie2 en functie2 roept functie1 op.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Voorbeeld
Om indirecte recursie te tonen, nemen we het volgende programma gebruikt om erachter te komen of een gegeven nummer even of oneven is van de gegeven invoer.
Code:
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();
)
)
Output:
Voorbeelden van recursie in Java
Hier zijn nog enkele voorbeelden om de problemen op te lossen met behulp van de recursiemethode.
Voorbeeld # 1 - Fibonacci-reeks
Van een reeks "n" -nummers wordt gezegd dat ze in een Fibonacci-reeks staan als nummer3 = nummer1 + nummer2, dwz elk nummer is een som van de voorafgaande twee nummers. Daarom begint de reeks altijd met de eerste twee cijfers zoals 0 en 1. Het derde cijfer is een som van 0 en 1 resulterend in 1, het vierde cijfer is de toevoeging van 1 en 1 resulterend in 2, en de reeks gaat door.
Bekijk de volgende code in Java om een Fibonacci-reeks te genereren:
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
)
)
Output:
Hier worden de eerste twee nummers geïnitialiseerd op 0 en 1 en afgedrukt. De variabelen "num1", "num2" en "num3" worden gebruikt om de vereiste volgorde te genereren. Variabele "num3" wordt verkregen door "num1" en "num2" toe te voegen en de nummers worden één positie naar links verschoven door te schudden zoals weergegeven in de code. De functie "Fibonacci" wordt hier recursief genoemd en bij elke iteratie wordt de waarde van "n" met 1 verlaagd. Vandaar dat de recursie wordt afgesloten zodra "n" waarde 0 bereikt.
Voorbeeld # 2 - Toren van Hanoi
Dit is een klassiek wiskundig probleem met 3 polen en een "n" aantal schijven met verschillende groottes. De puzzel gaat als volgt:
In het begin zullen de schijven zodanig zijn gerangschikt dat de grootste schijf zich allemaal aan de onderkant bevindt en de kleinste aan de bovenkant van de pool. Het doel is om deze schijven van de eerste naar de derde pool te verplaatsen en de schijven in dezelfde positie te houden als die in de eerste. Hier volgen enkele voorwaarden om in gedachten te houden bij het verplaatsen van deze schijven:
1. Per keer hoeft slechts één schijf te worden verplaatst.
2. In het proces is het plaatsen van een grotere schijf over een kleinere niet toegestaan.
3. De tweede (middelste) pool kan worden gebruikt om te bemiddelen tijdens het overbrengen van de schijven van de eerste naar de tweede pool.
Hierna volgt de Java-code die kan worden gebruikt om de puzzel op te lossen:
Code:
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);
)
)
)
Output:
Hier vertegenwoordigt de variabele "count" het aantal te gebruiken schijven. De functie "toren" is de recursieve functie die wordt gebruikt om de schijven van staaf 1 naar staaf 3 te verplaatsen. Een eenvoudige oplossing voor dit probleem kan worden gegeven door eerst 2 schijven te overwegen.
- Eerst beginnen we met het verplaatsen van disc1 van staaf 1 naar staaf 2.
- Vervolgens verplaatsen we disc2 naar staaf 3.
- Uiteindelijk eindigen we met het verplaatsen van disc1 naar staaf 3 om de vereiste oplossing te voltooien.
Hetzelfde principe wordt toegepast voor het "n" aantal schijven door de schijf van stang 1 naar 2 te verplaatsen (n-1) en dezelfde stappen te volgen als hierboven.
Voordelen van recursie in Java
- De code is gemakkelijk te schrijven en te onderhouden.
- De beste methode om de resultaten te vinden waar een groot aantal iteraties vereist zijn.
Nadelen van recursie in Java
- Recursieve functies gebruiken meer geheugen. Dit komt omdat elke keer een recursieve functie wordt aangeroepen; geheugentoewijzing wordt nieuw gedaan voor de variabelen op de stapel. En de respectieve geheugentoewijzing wordt vrijgegeven zodra de variabele waarden worden geretourneerd.
- Dit proces van geheugentoewijzing kost meer tijd, vandaar dat de uitvoering meestal traag is.
Conclusie
Recursieve functies zijn relatief eenvoudiger te coderen, maar ze zijn ook niet zo efficiënt in vergelijking met de andere bestaande methoden. Daarom worden ze vooral gebruikt in gevallen waarin de ontwikkelingstijd korter is en ook waar een aanzienlijk patroon in het probleem kan worden waargenomen.
Aanbevolen artikelen
Dit is een gids voor recursie in Java. Hier bespreken we de soorten recursie in Java, samen met de verschillende voorbeelden met de voor- en nadelen. U kunt ook de volgende artikelen bekijken voor meer informatie-
- JScrollPane in Java
- Wiskundige functies in Java
- Wiskundige functies in Java
- Constructor in Java
- Recursieve functie in Python
- Factorieprogramma in JavaScript