Cvičení 10: Rekurze

V tomto cvičení si budete zkoušet psát rekurzivní funkce a procvičíte si práci s ukazateli na funkce. V imperativním programování se snažíme většinou implicitní rekurzi vyhnout, protože velikost zásobníku bývá daleko menší než paměť, kterou je možné získat dynamickou alokací. V reálných programech je vhodné rekurzi přepsat do cyklu a použít explicitní zásobník. Je to sice víc práce a kód bude složitější, ale nehrozí takové riziko přetečení zásobníku. V tomto cvičení až na poslední úkol budete používat běžné rekurzivní volání.

Stáhněte si předpřipravený projekt jako obvykle z kontrového repozitáře. Dočasně můžete z tohoto archivu.
Existuje forma rekurze zvaná jako koncová rekurze. Taková rekurze vypadá tak, že rekurzivní volání je poslední příkaz v dané funkci. Výhodou použití takovéto rekurze je, že překladače při zapnuté optimalizaci umí (většinou) tuto rekurzi najít a nahradit ji za cyklus. Příklad takové rekurze může vypadat takto:
long factorial(int n)
{
    if (n > 1)
        return n * factorial(n - 1);
    return 1;
}
 
int arithmeticSum(int start, int stop, int step)
{
    if (start > stop)
        return 0;
    return start + arithmeticSum(start + step, stop, step);
}

V tomto cvičení ale tuto rekurzi nepoužijete.

Úkol 1: Jednoduché rekurzivní funkce

V rámci prvního úkolu bude potřeba implementovat tři jednoduché rekurzivní funkce, které prochází stromem a zjišťují nějaké informace.

Zadání úkolu 1

Implementujte funkci treeSum, která sečte hodnoty všech uzlů ve stromu.

int treeSum(const struct node *node);

Implementujte funkci treeSize, která spočítá počet uzlů ve stromě.

int treeSize(const struct node *node);

Implementujte funkci treeMaxValue, která zjistí nejvyšší hodnotu ve stromě.

int treeMaxValue(const struct node *node);
Všechny tři funkce jsou dost podobné. Pokud implementujete pořádně jednu funkci, zbývající dvě snadno vytvoříte z první funkce.

Úkol 2: Agregované rekurzivní funkce

Pokud jste úspěšně zvládli předchozí úkol, měli byste vidět výraznou podobnost funkcí treeSum a treeSize. Konkrétně jediný rozdíl je v chápání zobrazení hodnoty uzlu na číslo. V případě funkce treeSum se hodnota uzlu zobrazuje na sebe samu (tomu se říká identita). V případě funkce treeSize se každá hodnota uzlu zobrazuje vždy na hodnotu 1. Obecně lze tedy výpočet funkcí treeSum a treeSize sjednotit a zobrazení hodnoty uzlu na číslo se bude realizovat nějakou jinou funkcí (projekční funkce), kterou obdržíme jako parametr.

Zadání úkolu 2

Implementujte obecnou agregační funkci pro binární strom treeAggregate, která bude procházet strom a bude sčítat jednotlivá zobrazení hodnot uzlů.

int treeAggregate(const struct node *node, int(*projector)(int));

Pro výpočet velikosti stromu a součtu hodnot všech uzlů budete potřebovat následující projekční funkce:

int projectorSum(int value)
{
    return value;
}
int projectorSize(int value)
{
    (void)value;
    return 1;
}

Zkuste si napsat vhodné projekční funkce, které vám pomůžou zodpovědět následující otázky:

  1. Kolik je ve stromě čísel, která jsou dělitelná třemi?
  2. Je ve stromě více sudých, nebo lichých čísel?
  3. Jaký je počet všech cifer hodnot uzlů ve stromě?
Trik s přetypováním na void je použitý pouze z důvodu, aby si překladač nestěžoval, že se proměnná value ve funkci projectorSize nepoužívá.

Úkol 3: Obecná rekurzivní funkce

Funkce treeAggregate umožňuje procházet strom nezávisle na zobrazení hodnot uzlů. Problém s touto funkcí ale je, že kombinuje hodnoty zobrazení pomocí sčítání, a není možné pomocí funkce treeAggregate implementovat například funkci treeMaxValue. Proto vytvoříte obecnou rekurzivní funkci treeForEach, která bude umožňovat provádět libovolné (pouze čtecí) operace nad hodnotami ve stromě.

V případě funkce treeAggregate jste měli nějakou zobrazovací funkci, což ale pro případě funkce treeForEach nebude stačit. Nyní budete potřebovat zobrazovací funkci předat ještě nejaká data navíc, čímž se ze zobrazovací funkce stane operační funkce. Protože nelze dopředu určit jaký typ dat budou operační funkce potřebovat, použijete void *, který v každé operační funkci vhodně přetypujete.

Zadání úkolu 3

Implementujte obecnou rekurzivní funkci treeForEach, která bude procházet strom a bude postupně volat funkci, která bude operovat s hodnotou uzlu a dodatečnými daty.

void treeForEach(const struct node *node, void(*operation)(int, void *), void *dataPack);

Pro výpočet součtu hodnot ve stromě by mohla funkce operationSum a její použití vypadat nějak takto:

void operationSum(int value, void *dataPack)
{
    int *partialResult = (int *) dataPack;
    *partialResult += value;
}
 
int getTreeSum(const struct tree *tree)
{
    int result = 0;
    if (tree && tree->root)
        treeForEach(tree->root, operationSum, &result);
    return result;
}

Napište vhodné operační funkce, které vám pomohou zjistit následující věci:

  1. Implementujte zjištění maximální a minimální hodnoty ve stromě. (Pozor na počáteční hodnoty.)
  2. Zjištěte, kolik čísel ve stromě se nachází v intervalu [a; b], kdy rozsah intervalu zadává uživatel.
  3. Zjistěte, zda je z čísel ve stromě možné poskládat souvislou řadu po sobě jdoucích čísel.
Pokud chcete předávat operační funkci více věcí, je dobré si definovat nějakou strukturu, kterou vhodně naplníte. V operační funkci bude potřeba dataPack přetypovat na ukazatel na strukturu.

Úkol 4 (bonusový): Závorkový výpis stromu

Jedna z možností jak zapsat strom do sekvenčního zápisu je závorkový zápis. Tento zápis lze s úspěchem použít nejen pro binární, ale taktéž pro N-ární stromy. Ze zápisu

( 4 ( 2 * ( 3 ) ) ( 6 ( 5 ) * ) )

by vzniknul strom

      4
    /   \
  2       6
   \     /
    3   5

Znak hvězdy je použitý proto, aby bylo možné zjistit, který potomek uzlu je vynechaný. Akorát v případě, kdy uzel žádné potomky nemá, je zbytečné vypisovat dvě hvězdy.

Zadání úkolu 4

Vaším úkolem bude implementovat funkci, která na výstup vypíše strom v závorkové notaci. Aby věc nebyla jednoduchá, budete v tomto úkolu omezeni a budete muset použít explicitní zásobník. Funkce pro práci se zásobníkem máte připraveny v souborech stack.h a stack.c. Implementovaný zásobník umožňuje vkládat libovolná data, tj. pracuje s datovým typem void *. Pro implementaci výpisu tak budete muset i vhodně navrhnout strukturu, která bude popisovat rekurzivní procházení za použití explicitního zásobníku.

Níže je uvedená kostra funkce, kterou můžete použít. Místo otazníků je třeba doplnit vhodný kód:

void treeOutput(const struct tree *tree, FILE *output)
{
    struct stack stack;
    stackInit(&stack);
 
    if (tree && tree->root) {
         ???? initFrame = malloc(sizeof(????));
         initFrame->node = tree->root;
         ????
         stackPush(&stack, initFrame);
    }
 
    fputs("(", output);
    while (!stackEmpty(&stack)) {
         ???? frame = (????) stackTop(&stack);
 
         if (???) {
             ????
             free(frame);
             stackPop(&stack);
             continue;
         }
 
         ????
         /*
         print value of node?
         go to left? push left child on stack
         go to right? push right child on stack
         */
         ????
    }
}
Pokud budete chápat strom jako graf, je možné vnímat funkci treeOutput chápat jako upravený algoritmus DFS s modifikací, že z důvodu acykličnosti není třeba si pamatovat navštívené vrcholy grafu/uzly stromu.

Úlohu připravil Jiří Weiser – spito (zavináč) mail.muni.cz.

QR Code
QR Code public:pb071:cviceni10 (generated for current page)