Úvod do rekurzivní funkce v C
Proces opakování položek podobným způsobem, jako tomu bylo dříve, se nazývá rekurze. Funkce je řekl, aby byl rekurzivní jestliže to je voláno uvnitř sebe. Rekurze je podporována programovacím jazykem C. Níže jsou uvedeny dvě podmínky, které jsou rozhodující pro implementaci rekurze v jazyce C:
- Podmínka ukončení: Tato podmínka pomáhá funkci určit, kdy tuto funkci opustit. V případě, že nezadáme podmínku ukončení, kód vstoupí do nekonečné smyčky.
- Změna čítače: Změna čítače při každém volání této funkce.
Tímto způsobem můžeme implementovat rekurzivní funkci v programovacím jazyce C. Tyto funkce jsou užitečné pro řešení matematických problémů s penězi, které vyžadují, aby byl podobný proces několikrát nazýván. Příkladem takových problémů je výpočet faktoriálu řady generací řady Fibonacci.
Syntax:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Jak funguje rekurzivní funkce v C?
Rekurzivní funkce jsou způsob, jak implementovat rovnici do programovacího jazyka C. Rekurzivní funkce se volá s argumentem předaným do ní řekněme n, paměť v zásobníku je alokována jak lokálním proměnným, tak funkcím. Všechny operace obsažené ve funkci jsou prováděny pomocí této paměti. Pokud je splněna, je zkontrolována podmínka ukončení. Když kompilátor detekuje volání na jinou funkci, okamžitě přidělí novou paměť v horní části zásobníku, kde se vytvoří jiná kopie stejných lokálních proměnných a funkce. Zadejte stejný proces pokračuje.
Když se základní podmínka vrátí na true, konkrétní hodnota předaná volající funkci. Paměť přidělená této funkci bude vymazána. podobně se nová hodnota vypočítá ve volající funkci a IT se vrátí do super volací funkce. Tímto způsobem se uskuteční rekurzivní volání funkce odstranění dosáhne první funkce a celá paměť zásobníku se vymaže a výstup se vrátí. V případě, že základní funkce nebo podmínka ukončení není ve funkci zadána, může rekurzivní volání funkce vést k nekonečné smyčce.
Příklad rekurzivní funkce
Nyní uvidíme příklady rekurzivní funkce 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ýstup:
Vysvětlení výše uvedeného kódu
Výše uvedený příklad spočívá v nalezení faktoriálu čísla. Když hlavní funkce volá zábavu (4), je nejprve zkontrolována výstupní podmínka (4 == 1) a poté je vyvolána 4 * zábava (3). Znovu se zkontroluje základní podmínka (3 == 1). Podobně se vrátí 3 * je volána zábava (2) a to pokračuje až 2 * je volána zábava (1) a kde splňuje základní podmínku a vrací 1, pak volající funkce vrací 2 * 1, pak 3 * 2 * 1 a od prvního hovoru se vrací 4 * 3 * 2 * 1. Výsledkem je, že hlavní funkce ukládá 24 a tiskne je na výstup.
Přidělení paměti rekurzivní funkce
Každé volání funkce v jazyce c má za následek přidělení paměti v horní části zásobníku. Když se rekurzivní funkce nazývá paměť, je jí přidělena v horní části paměti, která byla přidělena volající funkci, a pro každé volání funkce se vytvoří všechny různé kopie lokálních proměnných.
Co je dosaženo základní podmínky, paměť přidělená funkci se zničí a ukazatel se vrátí k volající funkci? tento proces se opakuje a poté se vyvolá první volací funkce a nakonec se paměť zásobníku vyprázdní.
Ve výše uvedeném příkladu je pro výpočet faktoriálu čísla níže scénář pro přidělení paměti.
Krok 1
Krok 2
Krok - 3
Krok - 4
Krok - 5
Krok - 6
Krok - 7
Krok - 8
Krok - 9
Druhy rekurze
V programování C existují dva typy rekurze, které jsou uvedeny níže:
1. Recyklace ocasu a neocasí
Výše uvedený typ rekurze je vysvětlen níže:
- Ocasní rekurze
Je to typ rekurzivního volání funkce rekurze ve funkci, která je poslední akcí, která má být provedena při definici funkce. Znamená to, že rekurzivní volání nastane poté, co je implementována veškerá logika ve funkci.
Použití rekurze ocasu v našem programu při hansis výkonu programu a také snižuje využití paměti takovou funkcí. Je tomu tak proto, že jelikož byla do logiky přidělené volající funkci implementována jiná logika ve funkci, lze ji ze zásobníku vyjmout a znovu použít.
Kód:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Neurčená rekurze
Tento typ rekurzní rekurzivní koláže vytvořený uprostřed definice funkce. Pánská kalhotová rekurze je dokončena a hodnoty vrácené do volající funkce je třeba provést více kroků, takže nelze vymazat paměť.
Kód:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Přímá a nepřímá rekurze
Výše uvedený typ rekurze je vysvětlen níže:
- Nepřímá rekurze
K nepřímé rekurzi se říká, že nastane, když je určitá funkce rekurzivně nazývána médiem jiné funkce.
Kód:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Přímá rekurze
K přímé rekurzi se říká, že nastane, když je rekurzivní volání funkce provedeno v rámci její vlastní definice. “
Kód:
int fun1()(
fun1();
)
void main()(
fun1();
)
Závěr
Lze snadno usoudit, že rekurzivní funkce jsou nanejvýš důležité pro řešení matematických problémů, které vyžadují, aby byla všechna logika implementována opakovaně, dokud nebude splněna podmínka ukončení. Mnoho problémů, jako jsou Hanojské věže, stromové průchody, výpočet hloubky grafů.
Je důležité zmínit základní podmínku rekurzivní funkce. Požadavky na paměť a čas jsou pro rekurzivní program ve srovnání s iteračními programy větší, proto je nutné je používat opatrně.
Doporučené články
Toto je průvodce příkladem rekurzivní funkce v C. Zde diskutujeme práci, typy, přidělení paměti a příklady rekurzivní funkce v C. Další informace naleznete také v následujících článcích.
- Pole v programování v C
- Palindrom v programu C
- Vzory v programování C
- C vs C ++
- Palindrom v JavaScriptu
- Průvodce po sériích Fibonacci v JavaScriptu