Sissejuhatus Java rekursiivsesse funktsiooni
Rekursiivne funktsioon on see, mis helistab ühele või mitmele korrale. Rekursiivset funktsiooni kasutatakse olukordades, kus sama tulemust tuleb teha ikka ja jälle, kuni tulemus on saavutatud. See teeb mitu iteratsiooni ja probleemilause muutub iga iteratsiooniga lihtsamaks.
Rekursiivse funktsiooni kirjutamisel tuleb alati täpsustada baaslimiit. Vastasel korral põhjustab viga virna ülevoolu. Virn on mäluala, mis on reserveeritud meetodi kutsumiste säilitamiseks. Viga seisneb selles, et funktsiooni hakatakse pidevalt täitma, kuna see ei suuda leida piiranguid ja seega ammendab eraldatud mälu. Nii et virna ületäitumise vältimiseks määratleme teatavad baastingimused lausetega “kui… veel” (või mõne muu tingimusliku avaldusega), mis paneb rekursioonifunktsiooni peatama kohe, kui vajalik arvutus on lõpule viidud.
Rekursiooni tüübid Java-s
Java-vormingus on 2 tüüpi rekursiooni. Nemad on:
1. Otsene rekursioon
Süntaks:
Funktsioon1 kutsub ennast pidevalt, seega on rekursiivne funktsioon.
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
)
Näide
Arvu faktuur on näide otsest rekursioonist. Rekursiooni aluspõhimõte on keeruka probleemi lahendamine väiksemateks jagades. Näiteks arvutame arvu faktoriaal puhul i-faktori, kui teame selle i-1 faktoriaal.
Kood:
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));
)
)
Väljund:
2. Kaudne / vastastikune rekursioon
Funktsiooni1, mis kutsub teist funktsiooni2, mis omakorda kutsub funktsiooni1 kas otse või kaudselt, nimetatakse kaudseks rekursiivseks funktsiooniks.
Süntaks:
Vaatleme 2 funktsiooni, mida nimetatakse funktsiooniks1 () ja funktsiooniks2 (). Funktsioon 1 kutsub funktsiooni2 ja funktsioon2 kutsub funktsiooni1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Näide
Kaudse rekursiooni näitamiseks võtame järgmise programmi, mille abil saate teada, kas antud arv on antud sisendist paaris või paaritu.
Kood:
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();
)
)
Väljund:
Rekursiooni näited Java-s
Siin on veel mõned näited probleemide lahendamiseks rekursioonimeetodi abil.
Näide nr 1 - Fibonacci jada
Väidetavalt on n-numbrite komplekt Fibonacci jadas, kui number3 = arv1 + number2, st iga arv on selle kahe eelneva numbri summa. Seega algab järjestus alati kahe esimese numbriga nagu 0 ja 1. Kolmas number on 0 ja 1 summa, mille tulemuseks on 1, neljas number on 1 ja 1 liitmine, mille tulemuseks on 2, jada jätkub.
Fibonacci jada genereerimiseks vaadake Java-s järgmist koodi:
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
)
)
Väljund:
Siin lähtestatakse kaks esimest numbrit 0 ja 1 ning trükitakse. Muutujaid “num1”, “num2” ja “num3” kasutatakse vajaliku jada genereerimiseks. Muutuja “num3” saadakse, lisades “num1” ja “num2” ning numbreid nihutatakse nihutades ühte positsiooni vasakule, nagu näidatud koodis. Funktsiooni “Fibonacci” kutsutakse siin rekursiivselt ja iga iteratsiooni korral vähendatakse “n” väärtust ühe võrra. Seega rekursioon väljub kohe, kui “n” saavutab väärtuse 0.
Näide nr 2 - Hanoi torn
See on klassikaline matemaatiline ülesanne, millel on 3 poolust ja “n” arvu erineva suurusega kettaid. Mõistatus on järgmine:
Alguses on esimene pool kettad paigutatud nii, et neist kõige suurem ketas on allosas ja väikseim masti ülaosas. Eesmärk on viia need kettad esimeselt pooluselt kolmandale poolusele, hoides kettaid samas asendis nagu esimene. Järgnevalt on toodud mõned tingimused, mida nende ketaste nihutamisel meeles pidada:
1. Korraga tuleb teisaldada ainult üks ketas.
2. Protsessis pole suurema ketta asetamine väiksema peale lubatud.
3. Teist (keskmist) poolust saab kasutada vahendajana, ketaste teisaldamisel esimeselt teisele.
Järgnevalt on toodud Java-kood, mida saab kasutada mõistatuse lahendamiseks:
Kood:
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);
)
)
)
Väljund:
Muutuja “count” tähistab siin kasutatavate ketaste arvu. Funktsioon “torn” on rekursiivne funktsioon, mida kasutatakse ketaste teisaldamiseks vardast 1 varda 3 juurde. Sellele probleemile saab lihtsa lahenduse, kui kaaluda alguses kahte ketast.
- Esiteks alustame ketta1 nihutamist vardast 1 vardale 2.
- Järgmisena liigutame disc2 vardale 3.
- Lõpuks liigutame ketta1 varda 3 juurde, saades vajaliku lahenduse.
Sama põhimõtet rakendatakse n-arvu ketaste jaoks, liigutades (n-1) ketast vardast 1 kuni 2 ja järgides samasuguseid samme nagu ülal.
Rekursiooni eelised Java-s
- Koodi on lihtne kirjutada ja hooldada.
- Parim meetod tulemuste leidmiseks, kui on vaja suurt arvu iteratsioone.
Rekursiooni puudused Java-s
- Rekursiivsed funktsioonid kasutavad rohkem mälu. Seda seetõttu, et iga kord, kui kutsutakse rekursiivne funktsioon; mälu eraldamine toimub äsja virnas olevate muutujate jaoks. Ja vastav mälujaotus vabastatakse kohe, kui muutujate väärtused on tagastatud.
- See mälu eraldamise protsess võtab rohkem aega, seetõttu on täitmine tavaliselt aeglane.
Järeldus
Rekursiivseid funktsioone on suhteliselt lihtsam kodeerida, kuid need pole ka teiste olemasolevate meetoditega võrreldes nii tõhusad. Seetõttu kasutatakse neid enamasti juhtudel, kui arendamiseks on vähem aega ja ka siis, kui probleemis võib täheldada olulist mustrit.
Soovitatavad artiklid
See on Java rekursiooni juhend. Siin käsitleme Java rekursiooni tüüpe koos selle erinevate näidetega plusside ja miinustega. Lisateabe saamiseks võite vaadata ka järgmisi artikleid -
- JScrollPane Java
- Matemaatika funktsioonid Java keeles
- Matemaatika funktsioonid Java keeles
- Konstruktor Java
- Rekursiivne funktsioon Pythonis
- Faktoriprogramm JavaScriptis