Úvod do rekurzívnej funkcie v jazyku Java
Rekurzívna funkcia je funkcia, ktorá sa volá jeden alebo viackrát. Rekurzívna funkcia sa používa v situáciách, keď je potrebné vykonať tú istú skupinu operácií znova a znova, až kým sa nedosiahne výsledok. Vykonáva niekoľko iterácií a vyhlásenie o probléme sa s každou iteráciou stále zjednodušuje.
Pri písaní rekurzívnej funkcie musí byť vždy zadaný základný limit, inak to bude mať za následok chybu pretečenia zásobníka. Zásobník je oblasť pamäte vyhradená na udržiavanie vyvolania metód. Táto chyba je spôsobená tým, že funkcia sa začne vykonávať nepretržite, pretože nebude môcť nájsť limitujúci stav a tým vyčerpať pridelenú pamäť. Aby sme zabránili pretečeniu zásobníka, definujeme určité základné podmienky pomocou príkazov „if… else“ (alebo akýchkoľvek iných podmienených príkazov), ktoré spôsobia zastavenie rekurznej funkcie, len čo sa dokončí požadovaný výpočet.
Typy rekurzie v Jave
V Jave existujú 2 typy rekurzie. Oni sú:
1. Priama rekurzia
syntaxe:
Funkcia1 sa tu volá neustále, a preto je rekurzívna.
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
)
príklad
Faktor čísla je príkladom priamej rekurzie. Základným princípom rekurzie je vyriešenie zložitého problému rozdelením na menšie. Napríklad v prípade faktoriálu čísla vypočítame faktoriál „i“, ak poznáme jeho faktoriál „i-1“.
kód:
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ýkon:
2. Nepriama / vzájomná rekurzia
Funkcia1, ktorá volá inú funkciu2, ktorá na oplátku volá funkciu1 buď priamo alebo nepriamo, sa nazýva nepriama rekurzívna funkcia.
syntaxe:
Zvážte 2 funkcie nazývané function1 () a function2 (). Funkcia1 volá funkciu2 a funkcia2 volá funkciu1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
príklad
Aby sme ukázali nepriamu rekurziu, vezmeme nasledujúci program, ktorý slúži na zistenie, či je dané číslo od daného vstupu párne alebo nepárne.
kód:
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ýkon:
Príklady rekurzie v Jave
Tu je niekoľko ďalších príkladov na riešenie problémov pomocou metódy rekurzie.
Príklad č. 1 - Fibonacciho sekvencia
Hovorí sa, že množina čísel „n“ je vo Fibonacciho sekvencii, ak číslo 3 = číslo1 + číslo2, tj každé číslo je súčtom predchádzajúcich dvoch čísel. Preto postupnosť vždy začína prvými dvoma číslicami ako 0 a 1. Tretia číslica predstavuje súčet 0 a 1, ktorý vedie k 1, štvrté číslo je sčítanie 1 a 1, ktoré má za následok 2, a postupnosť pokračuje.
Ak chcete vygenerovať sekvenciu Fibonacci, vyskúšajte v jazyku Java nasledujúci kód:
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ýkon:
Prvé dve čísla sa tu inicializujú na 0 a 1 a tlačia sa. Premenné „num1“, „num2“ a „num3“ sa používajú na vygenerovanie požadovanej postupnosti. Premenná „num3“ sa získa pridaním „num1“ a „num2“ a čísla sa posunú o jednu pozíciu doľava premiešaním tak, ako je to znázornené v kóde. Funkcia „Fibonacci“ sa tu rekurzívne nazýva a pri každej iterácii sa hodnota „n“ zníži o 1. Preto rekurzia skončí, len čo „n“ dosiahne hodnotu 0.
Príklad č. 2 - Hanojská veža
Toto je klasický matematický problém, ktorý má 3 póly a „n“ počet diskov rôznych veľkostí. Hádanka je nasledovná:
Na začiatku bude mať prvý stĺp disky usporiadané tak, že najväčší z nich je na spodku a najmenší na vrchu stĺpa. Cieľom je presunúť tieto disky z prvého pólu do tretieho pólu tak, aby sa disky udržali v rovnakej polohe ako v prvom póle. Pri presúvaní týchto diskov je potrebné pamätať na niekoľko podmienok:
1. Naraz sa musí premiestniť iba jeden disk.
2. V tomto procese nie je dovolené umiestňovať väčší disk na menší.
3. Druhý (stredný) pól môže byť použitý na sprostredkovanie pri prenose diskov z prvého na druhý pól.
Nasleduje kód Java, ktorý možno použiť na vyriešenie hádanky:
kód:
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ýkon:
Premenná „počet“ tu predstavuje počet diskov, ktoré sa majú použiť. Funkcia „veža“ je rekurzívna funkcia, ktorá sa používa na premiestňovanie diskov z tyče 1 do tyče 3. Jednoduché riešenie tohto problému je možné dosiahnuť tak, že sa najprv vezmú do úvahy 2 disky.
- Najprv začneme pohybom disku 1 z tyče 1 do tyče 2.
- Ďalej presunieme disk2 na tyč 3.
- Nakoniec dokončíme presunutím disku 1 na tyč 3, čím sa dokončí požadované riešenie.
Rovnaký princíp sa uplatňuje na „n“ počet diskov pohybom (n-1) diskom z tyče 1 do 2 a postupovaním podobným spôsobom ako je uvedené vyššie.
Výhody rekurzie v Jave
- Kód je ľahko zapisovateľný a udržiavateľný.
- Najlepšia metóda na nájdenie výsledkov, kde sa vyžaduje veľké množstvo iterácií.
Nevýhody rekurzie v Jave
- Rekurzívne funkcie využívajú viac pamäte. Je to preto, že zakaždým, keď sa volá rekurzívna funkcia; alokácia pamäte sa vykonáva novo pre premenné v zásobníku. Akonáhle sa vrátia hodnoty premenných, uvoľní sa príslušné pridelenie pamäte.
- Tento proces prideľovania pamäte zaberie viac času, a preto je vykonávanie zvyčajne pomalé.
záver
Rekurzívne funkcie sú relatívne jednoduchšie na kódovanie, ale tiež nie sú také účinné v porovnaní s inými existujúcimi metódami. Preto sa používajú hlavne v prípadoch, keď je čas potrebný na vývoj kratší a tiež v prípadoch, keď je možné pozorovať výrazný obrazec problému.
Odporúčané články
Toto je príručka pre rekurziu v Jave. Tu diskutujeme typy rekurzie v Jave spolu s jej rôznymi príkladmi s výhodami a nevýhodami. Viac informácií nájdete aj v nasledujúcich článkoch
- JScrollPane v Jave
- Matematické funkcie v Jave
- Matematické funkcie v Jave
- Konštruktor v jazyku Java
- Rekurzívna funkcia v Pythone
- Faktorský program v JavaScripte