Diskusia – 2. diel - Stromová rekurzia - Generovanie všetkých možností

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

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

Odpovedať

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.

Odpovedať

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

Odpovedať

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!

Odpovedať

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');
                }
        }
}

Odpovedať

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.

Odpovedať

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?

Odpovedať

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.

Odpovedať

14.6.2023 9:33

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

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – 2. diel - Stromová rekurzia - Generovanie všetkých možností