Diskuze – Lekce 2 - Stromová rekurze - Generování všech možností

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře

Petr Kopecký

Člen

Petr Kopecký:11.6.2023 22:28

Tak se obávám že jsem narazil na limit mého chápání 😌

Odpovědět

11.6.2023 22:28

DarkCoder

Člen

DarkCoder:11.6.2023 23:13

Nedělej si z toho velkou hlavu. Jediné co potřebuješ znát je že něco takového existuje, leč v drtivé většině použiješ jiný způsob.

Z hlediska efektivity je totiž rekurzivní varianta obvykle méně efektivní než varianta bez rekurze. Rekurze má vyšší režii vytváření a zrušení rámce volání funkce, což může vést k většímu spotřebování paměti a pomalejšímu vykonávání programu.

Podívejme se na variantu bez rekurze pro výpis všech kombinací binárního čísla k-tého řádu.

void bin_cisla(int pole[], int k) {
        int pocet = 1 << k;  // počet kombinací (2^k)

        for (int i = 0; i < pocet; i++) {
                // Generování binárního čísla
                for (int j = 0; j < k; j++) pole[k - j - 1] = (i >> j) & 1;

                // Výpis binárního čísla
                for (int j = 0; j < k; j++) printf("%d", pole[j]);

                putchar('\n');
        }
}

Tato varianta bez rekurze využívá pouze jednoho cyklu, který iteruje přes všechny kombinace binárních čísel. Zápis jednotlivých bitů binárního čísla se provádí pomocí bitových operací, což je rychlý a efektivní způsob generování binárních čísel.

Při pohledu na funkci je vidět, jak je funkce lépe čitelná a srozumitelná než varianta pomocí rekurze.

Odpovědět

11.6.2023 23:13

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Petr Kopecký

Člen

Petr Kopecký:12.6.2023 7:03

díky za podporu a vysvětlení 😉

Odpovědět

12.6.2023 7:03

Jan Hnilica

Tvůrce

Jan Hnilica:13.6.2023 22:41

Já bych to být tebou nevzdával. Rekurze není úplně jednoduchá na pochopení, a každému dělá z počátku problémy. Ve skutečnosti ale potřebuješ překlenout jeden hlavní "aha!" moment, a pak už to půjde. Piš si prográmky, hraj si s tím, důležité je chápat, jak funguje zásobník a volání funkcí.

DarkCoder má sice pravdu, že reálně se s rekurzí potkáš málokdy, ale občas je to přesně to, co potřebuješ. Jsou i jiné problémy, než binární čísla... viz další díly (většinu jich teprve chystám, jde to pomalu).

Hodně zdaru!

Odpovědět

13.6.2023 22:41

DarkCoder

Člen

DarkCoder:14.6.2023 2:00

Nejlepší způsob jak pochopit rekurzi je vykrokovat si jednoduchou funkci.

Např. zde je funkce která vypíše řetězec pomocí rekurze.

void vypisRetezec(char* retezec) {
        if (*retezec == '\0') {
                return;  // Koncová podmínka rekurze - dosaženo konce řetězce
        }

        printf("%c", *retezec);  // Výpis aktuálního znaku
        vypisRetezec(retezec + 1);  // Rekurzivní volání pro zbytek řetězce
}

Normálně bys funkci pro výpis řetězce takto nenapsal. Ale uvedl jsem ji zde proto, že na ni lze pochopit chování rekurze. Pokud si funkci vykrokuješ v překladači jazyka C, pochopíš, co se tam děje.

Pro porovnání, funkce pro výpis řetězce bez použití rekurze:

void vypisRetezec(char *retezec) {
    while (*retezec != '\0') {
        printf("%c", *retezec);
        retezec++;
    }
}

Jinak funkce pro výpis podřetězců řetězce bez použití rekurze může vypadat takto:

void vypisPodretezce(char* retezec) {
        int delka = strlen(retezec);

        // Iterace přes všechny možné délky podřetězců
        for (int i = 1; i <= delka; i++) {

                // Iterace přes všechny možné začátky podřetězců
                for (int j = 0; j <= delka - i; j++) {

                        // Výpis aktuálního podřetězce
                        for (int k = 0; k < i; k++) {
                                putchar(retezec[j + k]);
                        }

                        putchar('\n');
                }
        }
}

Odpovědět

14.6.2023 2:00

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

DarkCoder

Člen

DarkCoder:14.6.2023 2:26

Abys porozuměl zásobníku a volání funkce, o kterých se zmiňoval Jan Hnilica, podívej se na následující funkci, která je lehkou modifikací rekurzivní funkce pro výpis řetezce.

void vypisRetezec(char* retezec) {
        if (*retezec == '\0') {
                return;  // Koncová podmínka rekurze - dosaženo konce řetězce
        }

        printf("%c", *retezec);  // Výpis aktuálního znaku
        vypisRetezec(retezec + 1);  // Rekurzivní volání pro zbytek řetězce

        printf("%c", *retezec);  // Opětovný výpis aktuálního znaku
}

Na této funkci Ti bude princip rekurze mnohem jasnější. Pokud funkci předáme např. řetězec "Test", funkce vypíš na obrazovku "TesttseT". Při cestě zpět se řízení programu předává té instanci volání funkce, která vyvolala novou instanci volání funkce. To je důvod, proč se při cestě zpět vypíše na obrazovku k řetězci ještě řetězec pozpátku.

Odpovědět

14.6.2023 2:26

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Petr Kopecký

Člen

Petr Kopecký:14.6.2023 6:34

Děkuji za vysvetleni. Tyto jednoduche varianty rekurze chápu, ale slozitejsi verze v druhe kapitole jsou myni na me prilis. Dovedu si u ni odvodit co udela, ale zatim netusim jak rekurzi napsat aby delala co potrebuji. To snad prijde cadem. Co zname * v atributu *retezec?

Odpovědět

14.6.2023 6:34

DarkCoder

Člen

DarkCoder:14.6.2023 9:33

Schopnost dokázat vytvářet algoritmy pomocí rekurze vyžaduje čas a velkou představivost. Pouze neustále cvičit a analyzovat rekurzivni algoritmy povede k tomu, že se to stane přirozenější.

V C se pracuje s ukazateli. * v parametrů značí že retezec je znakový ukazatel. Řetězce se v C předávají funkci pomocí ukazatele. Uvnitř funkce pak * znamená že se dereferencuje řetězec. To znamená, že se získá hodnota na adrese. Získá se tak první písmeno Řetězce. Retezec + 1 představuje ukazatel na další znak.

Odpovědět

14.6.2023 9:33

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.

Nejčastěji vyhledáváné

Diskuze – Lekce 2 - Stromová rekurze - Generování všech možností