Rekursioon
Mõiste vms kirjeldamine kasutades mõistet ennast
Programmeerimises: probleemi lahendamiseks kutsub funktsioon ennast välja
Selleks, et programm saaks lõpetada, peab rekursiivsel funktsioonil/meetodil olema lõpetamistingimus. Kui see puudub, on tegemist sisuliselt lõputu tsükliga (kuigi käivitades saame vea, mitte programm ei jää lõputult käima).
Rekursiooni abil jagatakse suur ülesanne väiksemateks tükkideks. Rekursiooni üks samm lahendab ära mingi väikese osa probleemist. Kui seda sammu korduvalt rakendada, lahendatakse suurem probleem.
Kõiki rekursiivseid funktsioone/meetodeid saab kirjutada iteratiivselt (for/while tsüklitega) ja vastupidi. See tähendab, et meetodi, mis prindib välja arvud 1st 10ni kasutades for-tsüklit, saab kirjutada rekursiivselt. Rekursiivse lahenduse puhul for-tsüklit kasutama ei pea. Samamoodi, igasuguse rekursiivse meetodi saab kirjutada iteratiivseks.
Rekursioon võimaldab paljudes olukordades kirjutada lühemat ja tihti ka arusaadavamat (kergemini loetavamat) koodi. Java keel kahjuks ei oska rekursiooniga optimaalselt hakkama saada. Seega, rekursiivne väljakutse on tavaliselt natuke aeglasem kui iteratiivne. See vahe on minimaalne (või olematu). Pigem valitakse rekursiivne lahendus seetõttu, et see on lühem ja selgem.
Sabarekursioon (tail recursion)
Sabarekursiooniks nimetatakse funktsiooni, kus rekursiivne väljakutse on viimane tegevus funktsioonis (funktsioon tagastab rekursiivse väljakutse tulemuse).
Näide sabarekursiooniga meetodist:
public static void tail(int index) {
if (index < 1) return; // B
System.out.println(index); // D
tail(index - 1); // C
}
public static void main(String[] args) {
tail(10); // A
}
Sellise meetodi saaks analoogselt kirjutada for-tsükliga:
for (int index = 10 /* A */; index >= 1 /* B */; index = index - 1 /* C */) {
System.out.println(index); /* D */
}
Kahes viimases näites on tähtedega A - D märgistatud koodiosad, mis sisuliselt kokku langevad.
Mõned näited
Minimaalne kood, mis kasutab rekursiivset väljakutset:
public class Example1 {
public static void f() {
f();
}
public static void main(String[] args) {
f();
}
}
Kood sisaldab lõputut tsüklit - meetod f() kutsub ennast lõputult välja. Käivitades saame StackOverflowError’i. See tuleneb sellest, et iga meetodi olek jäetakse meelde. Kui kõigepealt kutsutakse välja f(), siis jääb main() meetodi olek meelde. Esimene rekursiivne väljakutse jätab välimise f() meetodi oleku meelde jne. Kuigi antud näites olek on minimaalne (muutujaid jms ei sisalda), siis sellegipoolest saab mingi hetk pinu (stack) täis.
public class Example2 {
public static void f(int n) {
if (n < 1) {
System.out.println("Takeoff!");
} else {
System.out.println("T:" + n);
f(n - 1);
}
}
public static void main(String[] args) {
f(3);
}
}
Käivitamisel annab tulemuse:
T:3
T:2
T:1
Takeoff!
Kui muudame koodis kahe rea asukoha omavahel (else lauses):
public class Example3 {
public static void f(int n) {
if (n < 1) {
System.out.println("Takeoff!");
} else {
f(n - 1);
System.out.println("T:" + n);
}
}
public static void main(String[] args) {
f(3);
}
}
Saame tulemuseks vastupidise:
Takeoff!
T:1
T:2
T:3
Faktoriaali näide
Faktoriaal mingist arvust on kõikide arvude korrutis alates 1-st kuni selle arvuni:
Võttes arvesse eelnevat definitsiooni, proovime arvutada 4!. 4! = (4-1)! * 4 = 3! * 4. Selleks, et see tulemus välja arvutada, on meil vaja arvutada 3! väärtus. 3! = 2! * 3. Siin on omakorda vaja 2! tulemust. Pikalt võib lahti kirjutada:
4! = 3! * 4 =
= (2! * 3) * 4 =
= 2! * 3 * 4 =
= (1! * 2) * 3 * 4 =
= 1! * 2 * 3 * 4 =
= (0! * 1) * 2 * 3 * 4 =
= 1 * 1 * 2 * 3 * 4 = 24
Koodinäide:
public class Factorial {
public static int f(int n) {
if (n == 0) return 1;
return f(n - 1) * n;
}
public static void main(String[] args) {
System.out.println(f(6));
}
}
Annab tulemuseks:
720
Fibonacci jada
Esimesed arvud: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Kasutatakse ka varianti, kus esimene element on 0 ja teine 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Rekursiivne lahendus
Rekursiivne lahendus:
public class Fibo {
static int cnt = 0;
public static int fibo(int n) {
cnt++;
if (n < 3) return 1;
return fibo(n - 1) + fibo(n - 2);
}
public static void main(String[] args) {
System.out.println(fibo(11));
System.out.println("call count: " + cnt);
}
}
Selle programmi käivitamine annab tulemuseks:
89
call count: 177
Kui sama kood käivitada arvuga 40, saame tulmuseks:
102334155
call count: 204 668 309
(call count arv on loetavuse mõttes suurusjärkudeks jagatud)
Selleks, et proovida leida 50. elementi, peame muutma andmetüübi long-iks:
public class Fibo {
static long cnt = 0;
public static long fibo(int n) {
cnt++;
if (n < 3) return 1;
return fibo(n - 1) + fibo(n - 2);
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(fibo(50));
System.out.println("call count:" + cnt);
System.out.println(String.format("time: %.2f s", (System.currentTimeMillis() - start) / 1_000.0));
}
}
12586269025
call count: 25 172 538 049
time: 47.16 s
Iteratiivne lahendus
Kui võrdleme iteratiivse lahendusega:
public class FiboIterative {
public static long fibo(int n) {
long fib = 1; // current
long prev = 1; // previous
for (int i = 0; i < n - 2; i++) {
fib = fib + prev;
prev = fib - prev;
}
return fib;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(fibo(50));
System.out.println(String.format("time: %d ms", (System.currentTimeMillis() - start)));
}
}
Saame tulemuseks:
12586269025
time: 0 ms
Tsüklite arv: 48
Efektiivsem rekursiivne lahendus
Kasutame sama loogikat mis iteratiivse lahenduse puhul.
public class FiboTail {
public static long fibo(int n, long fib, long prev) {
if (n == 1) return prev;
return fibo(n - 1, fib + prev, fib);
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(fibo(50, 1, 1));
System.out.println(String.format("%d ms", (System.currentTimeMillis() - start)));
}
}
Selle käivitamisel saame:
12586269025
time 1 ms
fibo väljakutsete arv: 50 (vt järgnevat seletust).
Viimase koodinäidet täpsemalt vaadeldes võime mõelda nii:
igas väljakutses me vähendame
nväärtust. Kui alustatakse 50-ga, siis järgmise väljakutsega onnväärtus 49 jne. Seegafibomeetodit kutsutakse välja 50 korda. See on sama, mida saavutamefortsükliga (for (int n = 50; n >= 1; n--)).iga sammu korral antakse meetodi väljakutsesse uued väärtused. Võime mõelda nii:
fib = fib + prevjaprev = fib. Need on üldiselt samad mis iteratiivse väljakutse puhul. Iteratiivse väljakutse puhulprevväärtustamisel on kood natuke erinev. Seda seetõttu, et eelnevalt onfibväärtus juba ära muudetud (see onprevvõrra suurem). Siin rekursiivse väljakutse korral toimub väärtustamine samal hetkel, seetõttu ei peaprevväärtust maha lahutama.
Linke
Neljast videost koosnev seeria rekursioonist: https://www.youtube.com/playlist?list=PLwr2mqyA0RjawBkQkTmRcWfcptMC8ywLS
Lisalugemist: http://freecontent.manning.com/stack-safe-recursion-in-java/