Rekurzija u Javi

1. Uvod

U ovom ćemo se članku usredotočiti na temeljni koncept u bilo kojem programskom jeziku - rekurziju.

Objasnit ćemo karakteristike a rekurzivna funkcija i pokazati kako koristiti rekurziju za rješavanje različitih problema u Javi.

2. Razumjeti rekurziju

2.1. Definicija

U Javi podržava mehanizam poziva funkcije mogućnost samog poziva metode. Ova je funkcionalnost poznata kao rekurzija.

Na primjer, pretpostavimo da želimo zbrojiti cijele brojeve od 0 do neke vrijednosti n:

javni int zbroj (int n) {if (n> = 1) {return zbroj (n - 1) + n; } povratak n; }

Dva su glavna zahtjeva za rekurzivnom funkcijom:

  • Uvjet zaustavljanja - funkcija vraća vrijednost kada je zadovoljen određeni uvjet, bez daljnjeg rekurzivnog poziva
  • Rekurzivni poziv - funkcija se poziva s ulazni što je korak bliže stanju zaustavljanja

Svaki rekurzivni poziv dodati će novi okvir u memoriju steka JVM-a. Tako, ako ne obratimo pažnju na to koliko duboko naš rekurzivni poziv može zaroniti, može doći do iznimke bez memorije.

Ovaj potencijalni problem može se izbjeći korištenjem optimizacije rep-rekurzije.

2.2. Rekurzija repa nasuprot rekurziji glave

Rekurzivnu funkciju nazivamo: rep-rekurzijakada je rekurzivni poziv zadnja stvar koju funkcija izvršava. Inače je poznato kao rekurzija glave.

Naša provedba iznad iznos() funkcija je primjer rekurzije glave i može se promijeniti u rekurziju repa:

javni int tailSum (int currentSum, int n) {if (n <= 1) {return currentSum + n; } return tailSum (currentSum + n, n - 1); }

S rekurzijom repa, rekurzivni poziv je posljednje što metoda radi, tako da u trenutnoj funkciji nema više što izvršiti.

Dakle, logično nema potrebe za pohranjivanjem okvira stoga trenutne funkcije.

Iako je sastavljač limenka koristite ovu točku za optimizaciju memorije, treba napomenuti da Java kompajler za sada ne optimizira za rep-rekurziju.

2.3. Rekurzija naspram ponavljanja

Rekurzija može pojednostaviti provedbu nekih složenih problema čineći kôd jasnijim i čitljivijim.

No, kao što smo već vidjeli, rekurzivni pristup često zahtijeva više memorije jer se potrebna stek memorija povećava sa svakim rekurzivnim pozivom.

Kao alternativu, ako problem možemo riješiti rekurzijom, možemo ga riješiti i iteracijom.

Na primjer, naš iznos metoda može se implementirati pomoću iteracije:

javni int iterativeSum (int n) {int zbroj = 0; if (n <0) {return -1; } za (int i = 0; i <= n; i ++) {zbroj + = i; } povratna suma; }

U usporedbi s rekurzijom, iterativni pristup mogao bi potencijalno dati bolje performanse. To je rečeno, iteracija će biti složenija i teže razumljiva u usporedbi s rekurzijom, na primjer: prelazak binarnog stabla.

Donošenje pravilnog izbora između rekurzije glave, rekurzije repa i iterativnog pristupa ovisi o konkretnom problemu i situaciji.

3. Primjeri

Pokušajmo sada neke probleme riješiti na rekurzivan način.

3.1. Pronalaženje N-tog potencijala od deset

Pretpostavimo da moramo izračunati n-ta snaga od 10. Ovdje je naš ulaz n. Razmišljajući rekurzivno, možemo izračunati (n-1)-ta snaga od 10, a rezultat pomnožite s 10.

Zatim, za izračun (n-1)-ta snaga od 10 bit će (n-2)-ta snaga od 10 i pomnožite taj rezultat s 10 i tako dalje. Nastavit ćemo tako dok ne dođemo do točke u kojoj trebamo izračunati (n-n) -tu snagu 10, što je 1.

Ako bismo ovo željeli implementirati u Javi, napisali bismo:

javni int powerOf10 (int n) {if (n == 0) {return 1; } povratna snaga10 (n-1) * 10; }

3.2. Pronalaženje N-tog elementa Fibonaccijeve sekvence

Počevši sa 0 i 1, the Fibonaccijev niz je niz brojeva pri čemu je svaki broj definiran kao zbroj dva broja koja ga nastavljaju: 0 1 1 2 3 5 8 13 21 34 55

Dakle, s obzirom na broj n, naš problem je pronaći n-ti element od Fibonaccijev niz. Da bismo primijenili rekurzivno rješenje, moramo shvatiti Stop Condition i Rekurzivni poziv.

Srećom, stvarno je jednostavno.

Nazovimo f (n) the n-ta vrijednost niza. Onda ćemo imati f (n) = f (n-1) + f (n-2) ( Rekurzivni poziv).

U međuvremenu, f (0) = 0 i f (1) = 1 ( Stanje zaustavljanja).

Tada nam je zaista očito definirati rekurzivnu metodu za rješavanje problema:

javni int fibonacci (int n) {if (n <= 1) {return n; } vratiti fibonacci (n-1) + fibonacci (n-2); }

3.3. Pretvaranje iz decimalnog u binarno

Sada, razmotrimo problem pretvaranja decimalnog broja u binarni. Uvjet je primjena metode koja prima pozitivnu cijelu vrijednost n i vraća binarni Niz zastupanje.

Jedan od načina pretvaranja decimalnog broja u binarni je podijeliti vrijednost s 2, zabilježiti ostatak i nastaviti dijeliti količnik s 2.

Dijelimo tako dok ne dobijemo kvocijent od 0. Zatim, ispisujući sve ostatke u redu rezervi, dobivamo binarni niz.

Stoga je naš problem napisati metodu koja vraća ove ostatke u rezervnom redoslijedu:

javni String toBinary (int n) {if (n <= 1) {return String.valueOf (n); } povratak uBinary (n / 2) + String.valueOf (n% 2); }

3.4. Visina binarnog stabla

Visina binarnog stabla definirana je kao broj rubova od korijena do najdubljeg lista. Naš je problem sada izračunati ovu vrijednost za dano binarno stablo.

Jednostavan pristup bio bi pronalaženje najdubljeg lista, a zatim brojanje rubova između korijena i tog lista.

Ali pokušavajući smisliti rekurzivno rješenje, možemo ponoviti definiciju visine binarnog stabla kao maksimalnu visinu korijenove lijeve grane i korijenove desne grane, plus 1.

Ako korijen nema lijevu i desnu granu, njegova visina je nula.

Evo naše implementacije:

public int izračunatiDresto visine (korijen binarnog čvora) {if (root! = null) {if (root.getLeft ()! = null || root.getRight ()! = null) {return 1 + max (izračunatiTreeHeight (root.left), izračunajDrevo visine (korijen.desno)); }} return 0; }

Dakle, to vidimo neki se problemi mogu riješiti rekurzijom na vrlo jednostavan način.

4. Zaključak

U ovom uputstvu predstavili smo koncept rekurzije na Javi i demonstrirali ga s nekoliko jednostavnih primjera.

Provedbu ovog članka možete pronaći na Githubu.