====== 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.

===== Výchozí program v Javě =====
Zdrojové soubory, ze kterých budeme během tohoto cvičení vycházet, si stáhněte z archívu: {{courses:A0B36PR1:tutorials:09: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''.

===== Informace k procvičovanému tématu =====
==== Rekurze ====
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.

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

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

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

<code java>
private static void rekurze(int i) {
    if (i<5) {
        // do something...
        i++;
        rekurze(i);
    }
}

public static void main(String[] args) {
    rekurze(0);
}
</code>

==== Krokování programu ====
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.

{{courses:A0B36PR1:tutorials:09:debugbutton.png|}}
{{courses:A0B36PR1:tutorials:09:breakpoint.png|}}

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**.

{{courses:A0B36PR1:tutorials:09:debugmenu.png|}}

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í.

{{courses:A0B36PR1:tutorials:09:debug.png|}}

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.

{{courses:A0B36PR1:tutorials:09:debugcallstack.png|}}

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é).

{{courses:A0B36PR1:tutorials:09:debugvariables.png|}}
{{courses:A0B36PR1:tutorials:09:debugvariablehover.png|}}

===== Průběh cvičení =====
==== Část 1 ====
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).

<note important>Volání rekurzivní funkce ale není zadarmo. Každé další vnořené volání funkce zabírá určité místo v paměti (zásobníku). Zásobník není neomezený a může přetéct. Zkuste zvětšit proměnnou LIMIT a docílit přetečení zásobníku.</note>

==== Část 2 ====
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.

==== Část 3 ====
Implementujte rekurzivní funkci, která vypíše prvních ''n'' členů Fibonacciho posloupnosti. Viz [[http://cs.wikipedia.org/wiki/Fibonacciho_posloupnost]].
<note>Rekurzivní funkce může mít i více ukončovacích podmínek.</note>
<note important>Ačkoli rekurzivní zápis algoritmu může vypadat jednodušeji a přímočařeji, nemusí být vždy tou nejlepší volbou. Porovnejte rekurzivní výpočet s iterativním. Pomocí systémových funkcí porovnejte čas běhu dané funkce.</note>

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

==== Část 5 ====

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

==== Část 6 ====

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í).

{{courses:A0B36PR1:tutorials:09:goldenratio.png|}}

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).

{{courses:A0B36PR1:tutorials:09:e.png|}}

==== Část 7 ====

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).

==== Část 8 ====

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''


===== Domácí úkol =====
[[courses:a0b36pr1:hw:lab09|]]