Lisamaterjalid 3

Rekursioon

Rekursiooniga tutvusite kursusel „Programmeerimine“ ja see ei sõltu keelest. Javas on samuti rekursiivsed meetodid. Rekursioon tähendab, et meetod kutsub iseennast välja. Rekursiivsel meetodil on baas ja samm. Baasis meetodi uuesti välja ei kutsuta. Kui seda pole või selleni ei jõuta, siis on rekursioon lõpmatu, pinu ületäitub ja visatakse veateade StackOverflowError. Sammus jätkub rekursioon vähemalt ühekordse iseenda väljakutsega.

Vaatame meetodi, mis võtab argumendiks täisarvu n. Kui n-i väärtus on 0, siis tagastatakse 0. See on rekursiooni baas. Teistel juhtudel tagastatakse n + meetod1(n - 1). See on rekursiooni samm. Selle meetodi tulemuseks on summa arvudest vahemikus 0 kuni n.

public static int meetod1(int n) {
    if (n == 0) return 0; //baas
    return n + meetod1(n - 1); //samm
}

Kui n-i väärtus on 3, siis tagastatakse arv 6. Siin on sammud, mida rekursioon läbib:

meetod1(3)
3 + meetod1(2)
3 + (2 + meetod1(1))
3 + (2 + (1 + meetod1(0)))
3 + (2 + (1 + 0))
3 + (2 + 1)
3 + 3
6

Rekursioon läheb aina sügavamale, kuni see jõuab baasjuhuni, kus n-i väärtus on 0. Baasist hakkab rekursioon tagasi minema esimese väljakutseni ja lõpuks tagastab see arvu 6.

Järgmine meetod arvutab Fibonacci jada liikmeid. Jada esimesed kaks liiget on 0 ja 1. Selle võtame baasiks. Ülejäänud liikmed on eelmise kahe liikme summa ehk fibo(n - 1) + fibo(n - 2). Meetodi kahekordset väljakutset nimetatakse binaarseks rekursiooniks.

public static int fibo(int n) {
    if (n <= 1) return n; //baas
    return fibo(n - 1) + fibo(n - 2); //samm
}

Kui n-i väärtus on 4, siis tagastatakse arv 3. Teisisõnu Fibonacci jada viies arv on kolm. Rekursiooni sammud on järgnevad:

fibo(4)
fibo(3) + fibo(2)
(fibo(2) + fibo(1)) + fibo(2)
((fibo(1) + fibo(0)) + fibo(1)) + (fibo(1) + fibo(0))
((1 + 0) + 1) + (1 + 0)
(1 + 1) + 1
2 + 1
3

See on sarnane eelmisele meetodile, aga siin teostub kaheks hargnemine, kuni jõutakse baasini.

Kolmas meetod väljastab kõik täisarvudest koosneva massiivi alamhulgad nii, et nende liikmed on eraldatud liitmismärgiga. Kuna tagastama ei pea midagi, siis tagastustüübiks sobib void. Selleks, et kood oleks lihtsam defineerime abimeetodi meetod3Abi, mida kutsutakse välja algses meetodis meetod3. Abimeetodile saame anda lisaparameetreid, nagu indeks ja tühi sõne, mida täita ja lõpuks väljastada. Baasiks on massiivi kõigi elementide läbimine. Sammus tuleb teha kaks väljakutset. Üks, mis lisab massiivi arvu sõnesse ja teine, mis läheb seda tegemata edasi.

public static void meetod3(int[] massiiv) {
    meetod3Abi(massiiv, 0, "");
}

private static void meetod3Abi(int[] massiiv, int i, String sõne) {
    if (i > massiiv.length - 1) { //baas
        System.out.println(sõne);
    }
    else { //samm
        if (sõne.isEmpty()) {
            meetod3Abi(massiiv, i + 1, sõne + massiiv[i]);
        }
        else {
            meetod3Abi(massiiv, i + 1, sõne + " + " + massiiv[i]);
        }
        meetod3Abi(massiiv, i + 1, sõne);
    }
}

Anname meetodile ette massiivi {1, 2, 3}. Selle väljatrükk on järgnev:

1 + 2 + 3
1 + 2
1 + 3
1
2 + 3
2
3

Neljas meetod tagastab, kas täisarvude massiivis leidub otsitav arv. Selleks tuleb massiivi läbida ja iga kord võrrelda konkreetset elementi ning otsitavat. Massiivi läbimiseks defineerime abimeetodi, milles on indeks i lisaparameetrina. Baasjuhte on kaks. Kui massiiv on läbitud, siis pole midagi rohkem läbida ja tuleb tagastada false. Kui aga massiivis leidub õige väärtus, siis tagastada true. Sammuks on meetodi uus väljakutse, kus indeksi väärtust suurendatakse ühe võrra.

public static boolean meetod4(int[] massiiv, int otsitavArv) {
    return meetod4Abi(massiiv, otsitavArv, 0);
}

private static boolean meetod4Abi(int[] massiiv, int otsitavArv, int i) {
    if (i == massiiv.length - 1) return false; //baas
    if (massiiv[i] == otsitavArv) return true; //baas
    return meetod4Abi(massiiv, otsitavArv, i + 1); //samm
}

Siin on kaks näidet, kus esimeses massiivis leidub arv 21 ja teises mitte:
meetod4(new int[]{100, 21, 5}, 21) tagastab true.
meetod4(new int[]{100, 123, 5, 56}, 21) tagastab false.

Viimane meetod leiab massiivist kõige väiksema täisarvu. Defineerime abimeetodi meetod5Abi, kus on indeks massiivi läbimiseks. Meetodi Math.max abil saab võrrelda kahte arvu ja tagastada neist suurima. Sammuks sobib massiivi elemendi ja siiani suurima leitud arvu Math.max tagastus. Baasiks võtame kõige väiksema täisarvu Integer.MIN_VALUE, mille väärtus on -2147483648.

public static int meetod5(int[] massiiv) {
    return meetod5Abi(massiiv, 0);
}

private static int meetod5Abi(int[] massiiv, int i) {
    if (i == massiiv.length) return Integer.MIN_VALUE; //baas
    return Math.max(massiiv[i], meetod5Abi(massiiv, i + 1)); //samm
}

Vaatame olukorda, kus antakse meetodi argumendiks massiiv {6, 500, 1}:

meetod5(new int[]{6, 500, 1})
Math.max(6, meetod5Abi(massiiv, 1))
Math.max(500, meetod5Abi(massiiv, 2))
Math.max(1, meetod5Abi(massiiv, 3))
Math.max(1, Integer.MIN_VALUE)
Math.max(500, 1)
Math.max(6, 500)
500

Iga samm kutsutakse välja abimeetod, mis jõuab massiivi läbimisel baasini Integer.MIN_VALUE. Tagasi algusesse minnes võrreldakse siiani suurimat arvu ja massiivi kindlat elementi.

Enesekontroll