Linux C Programming Tutorial Část 18:Rekurzivní funkce

Bez ohledu na programovací jazyk, který používáte, jak začnete kódovat více a více, naučíte se koncepty, díky nimž bude váš kód ostrý a snadno čitelný/pochopitelný. Také v C existuje několik takových konceptů. Jednou z nich jsou „rekurzivní funkce“, o kterých budeme diskutovat zde v tomto článku.

Rekurzivní funkce je funkce, která volá sama sebe. Volání lze provést přímo z těla funkce nebo nepřímo z nějaké jiné funkce, kterou daná funkce volá.

Následuje příklad přímé rekurze:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

A zde je příklad nepřímé rekurze:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

Jak již bylo zmíněno na začátku, rekurze vám pomáhá dosáhnout kompaktního kódu, který se nejen snadno píše, ale také snadno rozumí a kontroluje. Vezměme si příklad, aby byla tato výhoda jasnější.

Jsem si jistý, že jste všichni museli slyšet o konceptu faktoriálu. Pro ty, kteří si toho nejsou vědomi, faktoriál je výsledek, který dostanete, když vynásobíte celé číslo se všemi kladnými celými čísly, které jsou menší. Například faktoriál 5 je 5x4x3x2x1, což se rovná 120.

Zde je jednoduchý kód pro nalezení faktoriálu čísla:

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Všimněte si, že tento kód slouží pouze k tomu, abyste věděli, jak lze faktoriál čísla vypočítat pomocí programu C. Program se nestará o rohová pouzdra, která mohou ovlivnit přesnost výsledku, který vytváří.

Toto je tedy jeden z mnoha způsobů, jak můžete vypočítat faktoriál čísla bez použití rekurzivní funkce. Nyní se podívejme na část kódu, který používá rekurzi k výpočtu faktoriálu.

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Takže vidíte, že funkce ‚faktoriál‘, která ve skutečnosti vypočítá faktoriál, je velmi kompaktní. A pokud budete pozorně sledovat, je to také velmi snadné pochopit.

Pro ty, kteří nevědí, co se děje, je hodnota, kterou uživatel zadal, řekněme 5, předána funkci 'factorial', když je poprvé volána z funkce 'main'. Uvnitř 'faktoriální' funkce je kontrola, zda je vstupní hodnota nula, což není pravda, když je funkce volána poprvé se vstupní hodnotou '5'.

Potom příkaz return obsahuje výraz, který se vynásobí 5 návratovou hodnotou 'faktoriální(4)'. Nyní se tedy funkce 'faktoriál' provede znovu a dostaneme se k následujícímu výrazu:return (4 * faktoriál(3)). A pak znovu tyto kroky opakujte.

Pokud se tedy podíváte zeširoka, zde je návod, jak se tato volání funkcí seskupují:

• 5 * faktoriál(4)
• 4 * faktoriál(3)
• 3 * faktoriál(2)
• 2 * faktoriál (1)
• 1 * faktoriál (0)

Nyní, když se faktorial(0) provede, podmínka 'if' ve funkci 'factorial' se stane pravdivou a vrátí se hodnota '1'. Nyní se tedy výše uvedená volání dokončí (porovnejte poslední položku v předchozím seznamu s první položkou v tomto seznamu atd.):

• 1 * 1
• 2 * (1*1)
• 3 * (2*(1*1))
• 4 * (3*(2*(1*1)))
• 5 *  (4 * (3*(2*(1*1))))

Což je ve skutečnosti 5 * 4 * 3 * 2 * 1, což je zase 120, faktoriál 5.

Takže takto fungují rekurzivní funkce. I když není pochyb o výhodách rekurzivních funkcí, které jsme dosud uvedli, existují i ​​​​některé nevýhody.

Například v našem příkladu výše, dokud nebylo dokončeno volání 'factorial(0)', všechna předchozí volání 'factorial' čekala na dokončení zpracování funkce. Nemluvě o tom, že automatické nebo lokální proměnné zabírají paměť pro každé uskutečněné rekurzivní volání.

Při použití rekurze tedy prakticky nedochází k žádné úspoře úložného prostoru. Navíc neexistuje žádná záruka, že váš kód bude rychlejší při provádění. Skutečná výhoda rekurzivní funkce je, když se zabýváte datovými strukturami, o kterých budeme diskutovat později v rámci této pokračující série C tutoriálů.

Závěr

Na závěr, i když rekurzivní funkci možná nepoužíváte často ve svých každodenních úlohách kódování, je to důležitý koncept, kterého si musíte být vědomi. Vyzkoušejte příklad, který jsme zde zmínili, a vylaďte jej, abyste ještě lépe porozuměli konceptu rekurzivních funkcí.