Rekursioon, näide: Hanoi tornid. Rekursiooni eemaldamine, "sabarekursioon" (tail recursion).
Hanoi tornid
On n erineva läbimõõduga ketast, augud keskel, ning kolm varrat, millele kettaid saab laduda. Igal käigul tohib võtta ühe ketta ning tõsta selle mingile teisele vardale, kuid suuremat ketast ei tohi kunagi asetada väiksema peale. Eesmärgiks on laduda "torn" ainult lubatud käikude abil ühelt vardalt teisele (kolmandat varrast abiks võttes).
Osutub, et ülesanne on eksponentsiaalse ajalise keerukusega ketaste arvu suhtes.
Arutluskäik:
Baasjuht: kui ketaste arv on null, siis ei ole tarvis mitte midagi teha.
Samm: kui oskame laduda k-1 ketast vardalt a vardale b, siis k ketta ladumiseks vardalt x vardale z tuleb:
1. laduda k-1 ketast vardalt x vardale y (võimalik eelduse põhjal)
2. tõsta suurim ketas (k) vardalt x vardale z "põhjaks"
3. laduda needsamad k-1 ketast vardalt y vardale z (võimalik eelduse põhjal)
On oluline, et algseis (ja tegelikult ka mistahes järgnev seis) oleks lubatav.
kood
public static void hanoi (int n, int x, int y, int z) {
if (n > 0) {
hanoi (n-1, x, z, y);
System.out.print (String.valueOf(x) + ">" + String.valueOf(z) + " "); // tõste
hanoi (n-1, y, x, z);
}
}