9 - Rekurze

Cílem tohoto cvičení je osvojit si programování rekurzivních funkcí. Na nich si ukážeme výhody krokování programu v debugovacím režimu.

Zdrojové soubory, ze kterých budeme během tohoto cvičení vycházet, si stáhněte z archívu: pr1-lab09.zip . Stejně jako v minulých cvičeních si v Netbeans vytvořte projekt pr1-lab09 a přidejte do něj adresář src se zdrojovými soubory. Jako např. v 7. cvičení i zde je hlavní třída Start, která volá metodu Start() třídy Lab09. Jednotlivé části programu (part1(), part2(),…) lze volit přímým zadáním prvního argumentu nebo pomocí konstanty DEFAULT_PART. Domácí úkol se pak spouští změnou konstanty HOMEWORK ve třídě Start.

Rekurzivní funkce je funkce, která volá samu sebe. To by samo o sobě znamenalo nekonečné zacyklení. Proto je potřeba ukončovací podmínka, která včas zastaví další volání funkce. Ukončovací podmínka typicky kontroluje stav parametru, který se mění s každým dalším voláním rekurzivní funkce. Užitečný kód (v příkladu do something) pak může být vykonáván před či po rekurzivním volání funkce v závislosti na účelu dané funkce.

public void funkce(parametr) {
    if (ukončovací podmínka) return;
    else {
        // do something...
        funkce(změněný parametr);
        // do something...
    }
}

For cyklus se také dá zapsat jako rekurzivní funkce. Porovnejte následující dva příklady.

public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
        // do something...
    }
}

private static void rekurze(int i) {
    if (i<5) {
        // do something...
        i++;
        rekurze(i);
    }
}
 
public static void main(String[] args) {
    rekurze(0);
}

Pokud si nejste jisti, co vlastně program dělá, nebo máte pocit, že by měl dělat něco jiného, můžete použít ladící (debugovací) režim, kde lze běh programu pozastavit a krokovat řádek po řádku.

Jednou z možností je označit si v kódu ty řádky, na kterých se má program zastavit (breakpointy). To lze udělat jednoduše kliknutím na číslo dané řádky. Objeví se zde červený čtvereček a celý řádek se zvýrazní. Program je pak nutno spustit tlačítkem Debug Main Project (Ctrl+F5) jako na obrázku níže. Při běžném spuštění (zeleným trojúhelníkem) jsou breakpointy ignorovány.

Další možností je kliknout v debug toolbaru (obr. níže) na Step Into (F7) (program se zastaví hned na prvním řádku kódu), nebo Run To Cursor (F4) (program se zastaví až v místě, kde je kurzor - jako by tam byl breakpoint). Pokud debug toolbar nevidíte, lze jej zobrazit přes menu View→Toolbars→Debug.

Pro krokování programu jsou k dispozici intuitivní tlačítka v debug toolbaru. Zelený řádek označuje místo, kde je program zastaven. Fialové řádky jsou místa, kde se program zanořil do dalších funkcí.

Během debugování (krokování) programu máme k dispozici další přehledy. Například Call stack (volání funkcí). Tento přehled je dostupný na dvou místech přes menu Window→Debugging→Call Stack / Debugging. Když se v programu zavolá funkce, přidá se na vrch call stacku. Po skončení funkce z call stacku zmizí. Call stack tedy znázorňuje, jak a odkud (číslo řádku) byly funkce volány. Můžeme se tak dopátrat, kudy se program dostal do stavu, ve kterém jsme ho pozastavili.

Nebo přehled proměnných (dostupné přes Window→Debugging→Variables). Aktuální hodnotu proměnné lze získat i po najetí myší na název dané proměnné (funguje pouze pro lokálně dostupné proměnné).

Výpočet faktoriálu je ideální pro názorné použití rekurzivní funkce. Ze známé vlastnosti faktoriálu n!=n*(n-1)! vidíme, že k výpočtu faktoriálu můžeme použít hodnotu jiného faktoriálu. Jelikož víme, že 0!=1, máme i požadovanou ukončovací podmínku.

Na příkladu výpočtu faktoriálu si vyzkoušejte krokování programu. Například najetím myší na danou proměnou se ukáže její hodnota (program musí být zastaven ve stejné funkci). Aktuálně dostupné proměnné a jejich hodnoty lze najít i v okně Variables ve spodní části obrazovky (menu Window→Debugging→Variables).

Napište rekurzivní funkci, která vypíše na obrazovku zadaný počet hvězdiček. Lze to napsat i for-cyklem, ale zde použijte rekurzi.

Implementujte rekurzivní funkci, která vypíše prvních n členů Fibonacciho posloupnosti. Viz http://cs.wikipedia.org/wiki/Fibonacciho_posloupnost.

Implementujte rekurzivní funkci na testování palindromů. Využijte dekompozici po vzoru faktoriálu. (Nápověda : Co se skrývá uvnitř palindromu?)

Osvěžte si znalosti z přednášky a zkuste implementovat rekurzivní algoritmus k řešení hlavolamu Hanojských věží.

Implementujte výpočet postupné aproximace zlatého řezu, vyjádřeného pomocí nekonečného rozvoje. Ukončovací podmínka zde bude vyjadřovat požadovanou přesnost výpočtu (počet zanoření).

Výpočet eulerova čísla lze také výjádřit nekonečnou řadou. To lze implementovat dokonce pomocí dvojnásobné rekurze (jedna pro faktoriál, druhá pro postupnou aproximaci).

Implementujte převodník čísel, který vypíše na obrazovku zadané číslo z desítkové soustavy převedené do libovolné jiné soustavy (max. je 35 znaková soustava 0-9A-Z).

Představte si klasickou hru Hledání min (minesweeper). Jak byste program realizovali? Pro inspiraci můžete zkusit on-line verzi hry http://minesweeperonline.com.

Pro tuto úlohu máte předpřipraveny dvě samostatné třídy v souborech Minesweeper.java a MineField.java.

Třída MineField je hotová a zakrývá (zaobaluje) práci s vnitřní reprezentací minového pole. Třída poskytuje několik public funkcí, pomocí kterých se dá k minovému poli přistupovat zvenčí (např. ze třídy Minesweeper). Všechny funkce mají dvojí rozhraní, kdy se souřadnice v minovém poli dají vyjádřit buď pomocí dvou celých čísel (int x, int y) nebo pomocí jednoho objektu, který tyto souřadnice obsahuje (Point p). Minové pole je čtvercové a má zadanou velikost SIZE x SIZE. Souřadnice políček se pohybují v intervalu <1,SIZE>.

Třída Minesweeper hotová není a obsahuje jenom nástřel možné implementace. Je tu několik metod, které je ještě potřeba implementovat:

• náhodné rozmístění min - randomizeField
• chování programu po kliknutí na políčko - clickOn
• odkrývání políček - reveal
• vyhledání souřadnic okolních políček - getAdjacentSpots
• kontrola jestli jsou souřadnice stále uvnitř pole - isInsideField
• kontrola jestli je hra vyhraná - jsou odkryta všechna políčka, kde nejsou miny - checkWin

lab09