Úvod do rekurzívnej funkcie v C
Proces opakovania položiek podobným spôsobom, aký bol predtým, sa nazýva rekurzia. Funkcia sa považuje za rekurzívnu, ak sa volá sama osebe. Rekurzia je podporovaná programovacím jazykom C. Nižšie sú uvedené dve podmienky, ktoré sú rozhodujúce pre implementáciu rekurzie v jazyku C:
- Podmienka ukončenia: Táto podmienka pomáha funkcii identifikovať, kedy ukončiť túto funkciu. V prípade, že nešpecifikujeme podmienku ukončenia, kód vstúpi do nekonečnej slučky.
- Zmena počítadla: Zmena počítadla pri každom volaní na túto funkciu.
Týmto spôsobom môžeme implementovať rekurzívnu funkciu v programovacom jazyku C. Tieto funkcie sú užitočné na riešenie matematických problémov s peniazmi, ktoré vyžadujú, aby sa podobný proces nazýval niekoľkokrát. Príkladom takýchto problémov je výpočet faktoriálu generovania radu Fibonacciho sérií.
syntaxe:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Ako funguje rekurzívna funkcia v C?
Rekurzívne funkcie sú spôsobom, ako implementovať rovnicu do programovacieho jazyka C. Rekurzívna funkcia sa volá s argumentom, ktorý sa do nej odovzdáva povedzme n, pamäť v zásobníku je alokovaná miestnym premenným, ako aj funkciám. Všetky operácie prítomné vo funkcii sa vykonávajú pomocou tejto pamäte. Podmienka pre výstup je skontrolovaná, ak je splnená. Keď kompilátor zistí volanie na inú funkciu, okamžite pridelí novú pamäť v hornej časti zásobníka, kde sa vytvorí odlišná kópia rovnakých miestnych premenných a funkcia. Rovnaký proces pokračuje.
Keď sa základná podmienka vráti na true, konkrétna hodnota odovzdaná volajúcej funkcii. Pamäť pridelená tejto funkcii sa vymaže. podobne sa nová hodnota vypočíta vo volajúcej funkcii a IT sa vráti do super volacej funkcie. Týmto spôsobom sa uskutočnia rekurzívne hovory na odstránenie funkcie dosiahne prvú funkciu a celá pamäť zásobníka sa vymaže a výstup sa vráti. Ak vo funkcii nie je zadaný základný stav alebo výstupný stav, rekurzívne volania funkcie môžu viesť k nekonečnej slučke.
Príklad rekurzívnej funkcie
Teraz uvidíme príklady rekurzívnej funkcie v C
kód:
#include
int fun(int n)
(
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as it's argument .
//The value returned is multiplied with the argument passed in calling function.
)
int main()(
int test=4;
int result =0;
result =fun(test);
printf("%d", result);//prints the output result.
)
Výkon:
Vysvetlenie vyššie uvedeného kódu
Uvedeným príkladom je nájdenie faktoriálu čísla. Keď hlavná funkcia volá zábavu (4), najskôr sa skontroluje výstupná podmienka (4 == 1) a potom sa vyvolá 4 * zábava (3). Opäť sa skontroluje základná podmienka (3 == 1). Podobne sa vráti 3 * je volaná zábava (2) a to pokračuje až do 2 * je volaná zábava (1) a kde spĺňa základné podmienky a vracia 1, potom volaná funkcia vráti 2 * 1 potom, 3 * 2 * 1 a od prvého hovoru sa vráti 4 * 3 * 2 * 1. Výsledkom je, že hlavná funkcia ukladá 24 a tlačí ich na výstupe.
Priradenie rekurzívnej funkcie k pamäti
Každé volanie funkcie v jazyku c má za následok pridelenie pamäte v hornej časti zásobníka. Keď sa rekurzívna funkcia nazýva pamäťou, je jej pridelená v hornej časti pamäte, ktorá bola priradená volajúcej funkcii, so všetkými rozdielnymi kópiami miestnych premenných sa pre každé volanie funkcie vytvorí.
Aká je dosiahnutá základná podmienka, pamäť pridelená funkcii sa zničí a ukazovateľ sa vráti k volajúcej funkcii? tento proces sa opakuje po prvej volacej funkcii a nakoniec sa pamäť zásobníka vyprázdni.
Vo vyššie uvedenom príklade je na výpočet faktoriálu čísla nižšie scenár pre pridelenie pamäte.
Krok 1
Krok 2
Krok - 3
Krok - 4
Krok - 5
Krok - 6
Krok - 7
Krok 8
Krok - 9
Druhy rekurzie
V programovaní C existujú dva typy rekurzie, ktoré sú uvedené nižšie:
1. Rekurzia chvosta a chvosta
Vyššie uvedený typ rekurzie je vysvetlený nižšie:
- Rekurzia chvosta
Je to typ rekurzívneho volania rekurzie vo funkcii, ktorá je poslednou akciou, ktorá sa má vykonať pri definovaní funkcie. Prostriedky rekurzívne volanie sa objaví po implementácii všetkej logiky vo funkcii.
Použitie rekurzie chvosta v našom programe hansis výkon programu a tiež znižuje využitie pamäte tak funkcie. Je to tak preto, že keďže iná logika vo funkcii bola implementovaná do pamäte pridelenej volajúcej funkcii, môže byť zo zásobníka odstránená a znovu použitá.
kód:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Neurčená rekurzia
Tento typ rekurzívnej rekurzívnej koláže vytvorenej uprostred definície funkcie. Pánska nohavičková rekurzia je dokončená a hodnoty vrátené do volacej funkcie je potrebné vykonať ešte viac krokov, takže pamäť sa nedá vymazať.
kód:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Priama a nepriama rekurzia
Vyššie uvedený typ rekurzie je vysvetlený nižšie:
- Nepriama rekurzia
Nepriama rekurzia sa uvádza, keď nastane, keď sa určitá funkcia rekurzívne nazýva médiom inej funkcie.
kód:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Priama rekurzia
Priama rekurzia sa uvádza, keď nastane rekurzívne volanie funkcie v rámci jej vlastnej definície. “
kód:
int fun1()(
fun1();
)
void main()(
fun1();
)
záver
Možno ľahko vyvodiť záver, že rekurzívne funkcie sú nanajvýš dôležité pre riešenie matematických problémov, ktoré vyžadujú, aby sa všetky podobné logické postupy implementovali opakovane až do splnenia podmienky ukončenia. Mnoho problémov, ako sú veže v Hanoji, prierezy stromov, výpočet hĺbky grafov.
Je dôležité spomenúť základnú podmienku rekurzívnej funkcie. Požiadavky na pamäť a čas sú v prípade rekurzívneho programu väčšie ako v prípade iteračných programov, a preto sa musia používať opatrne.
Odporúčané články
Toto je sprievodca príkladom rekurzívnej funkcie v C. Tu diskutujeme o práci, druhoch, alokácii pamäte a príkladoch rekurzívnej funkcie v C. Môžete sa tiež pozrieť na nasledujúce články, aby ste sa dozvedeli viac -
- Polia v programovaní C
- Palindróm v programe C
- Vzory v programovaní C
- C vs C ++
- Palindróm v JavaScripte
- Sprievodca sériami Fibonacci v jazyku JavaScript