Faktoriál

Z matematiky víme, že faktoriál čísla n (značeno jako n!) je roven součinu všech přirozených čísel menších nebo rovných n (přičemž platí 0! = 1) např. 3! = 3*2*1 = 1*2*3 = 6. Z předchozí číselné rostoucí řady vidíme, že se jedná o součin hodnot, které postupně stoupají o hodnotu 1 až do konečné prvku této řady představující zadané číslo uživatelem - viz Obrázek 1. Vidíme, že čísla také mohou klesat od čísla n až do 1 - tímto možným přístupem se však nyní nebudeme zabývat.

Obrázek 1: Princip faktoriálu - součin řady zvyšujících se čísel

Matematicky bychom při násobení čísel mezi sebou postupovali např. zleva doprava (lze i opačně), tedy 1*2 = 2 a pak tento výsledek 2 násobíme 3, tedy 2*3 = 6. Jedná se tedy o pravidelný postup, na který lze uplatnit cykly. Součin všech prvků lze rozdělit do jednotlivých iterací, kde v každé iteraci je provedeno násobení hodnoty součinu z předchozí iterace (náš předchozí výsledek součinu uložený v proměnné f) aktuálním číslem (uloženým v proměnné i), tj. f * i. Výsledek tohoto součin budeme ukládat do proměnné f (hodnota v f tedy bude v každé iteraci přepisována), tedy f = f * i. Aktuální číslo uložené v proměnné i je následně zvětšeno o hodnotu 1, tj. i + 1, abychom jej mohli využít v součinu v další iteraci. Myšlenku v předchozí větě aplikujeme na příklad našeho faktoriálu, tj. 3! = 1*2*3. 

V první iteraci je v proměnné f a v proměnné i uložena počáteční hodnota 1. V první iteraci je tedy f = f * i = 1*1 = 1. Následně zvedneme hodnotu i o 1, tj. i = i + 1 = 1 + 1 = 2. V další iteraci provedeme součin f = f * i = 1*2 (vidíme že jde o první dva členy v součinu všech čísel v rozepsané rovnici faktoriálu). Hodnotu součinu si uložíme do proměnné f, abychom ji mohli využít v další iteraci. Ještě než přejdeme do další iterace, musíme inkrementovat aktuální číslo z hodnoty 2 na hodnotu 3. V další iteraci tedy násobíme f = 2*3 (hodnota v f * hodnota aktuálního čísla v i). Tato iterace byla poslední, protože aktuální číslo je rovnu číslu, pro něhož jsme chtěli vypočítat faktoriál - viz Obrázek 2. 

Všimněte si, že počet iterací je roven 3, což je naše číslo, pro něhož počítáme faktoriál. Všimněte si, že bychom také mohli vynechat první iteraci, pokud bychom inicializovali proměnnou i hodnotou 2. Pak by namísto 3 iterací bylo zapotřebí pouze 2 iterací.

Obrázek 2: Princip výpočtu faktoriálu

Tento princip využijeme ve volaných podprogramech - funkcích, které navracejí do hlavního programu vypočtenou hodnotu faktoriálu. Tyto funkce jsou volány z hlavního programu - viz Obrázek 1. 

Obrázek 3: Hlavní program Faktorial pro výpis faktoriálu

První volanou funkcí je FaktorialWhile. Tento podprogram využívá cyklu while, v jehož těle je implementována podstata násobení jednotlivých prvků řady. Počátečním krokem je inicializace obou proměnných i a f  na hodnotu 1. V lokální proměnné i je uloženo aktuální číslo, které využíváme v součinu f * i prováděného v každé iteraci. Výsledek tohoto součinu stávající hodnoty f z předchozí iterace a aktuálního čísla i je uložen do proměnné f. V každé iteraci je tedy hodnota v proměnné f přepsána novou hodnotou součinu. Jako následný krok je provedena inkrementace aktuálního čísla i o hodnotu 1 - viz Obrázek 4. 

 Obrázek 4: Podprogram FaktorialWhile - funkce pro výpočet faktoriálu pomocí cyklu s podmínkou na začátku

Dalším podprogramem (funkcí) využívající cyklus je FaktorialDoWhile, který má svém těle implementován cyklus s podmínkou na konci - viz Obrázek 5. Podstata podprogramu je téměř stejná jako v předchozím podprogramu FaktorialWhile.

Obrázek 5: Podprogram FaktorialDoWhile - funkce pro výpočet faktoriálu pomocí cyklu s podmínkou na konci

Vzhledem k tomu, že víme, kolikrát iterací má proběhnout v cyklu, lze použít v dalším podprogramu FaktorialFor cyklus s krokem - viz Obrázek 6. Inicializace řídící proměnné cyklu probíhá před první iterací cyklu. Inkrementace řídící proměnné cyklu probíhá po proběhnutí iterace, taktéž v bloku for.   

 Obrázek 6: Podprogram FaktorialDoWhile - funkce pro výpočet faktoriálu pomocí cyklu s krokem

Posledním podprogramem je FaktorialVolaniRekurze. Podprogram je taktéž funkce, která v sobě volá další funkci pro výpočet faktoriálu pomocí rekurze - FaktorialRekurze - viz Obrázek 7.

Obrázek 7: Podprogram FaktorialVolaniRekurze - volání funkce s rekurzí

Pomocí rekurze bychom mohli faktoriál kladného čísla rozepsat jako 3! = 3*2!, kde bychom 2! uvnitř výrazu mohli zase rozepsat 2! = 2*1! a další rozepsání již není zapotřebí, protože 1! je roven 1. Postupným zpětným dosazením nám tedy vznikl výraz 3! = 3*2*1!, tedy 3! = 3*2*1 = 6. Výpočet faktoriálu rekurzivním způsobem, lze zapsat jako n*(n-1)! . Pokud bychom použili metodu pro výpočet faktoriálu, nazvěme ji např. FaktorialRekurze, můžeme náš předchozí zápis výpočtu faktoriálu rekurzivním způsobem zapsat jako n*FaktorialRekurze(n-1). Tohoto principu využijeme v následující funkci využívající princip rekurze - viz Obrázek 8.

Obrázek 8: Podprogram FaktorialRekurze - funkce pro výpočet faktoriálu pomocí rekurze

V těle této funkce je definována podmínka, která určuje, kdy se vnořování funkce do sebe samé musí zastavit, tzn., že krok, kdy se funkce postupným snižováním parametru na základě výrazu (n – 1), dostane až do stavu, kdy je předávaná hodnota parametru rovna 0 (tehdy je 0! = 1). Je také možností zastavit vnořování funkce již o jednu iteraci dříve, tj. kdy je předávaná hodnota parametru rovna 1 (protože 1! = 1). Uživateli jsme však dali možnost vypočítat faktoriál pro číslo z definičního oboru přirozených čísel, proto povolíme i vložení 0.

Samotnou rekurzi vidíme ve větvi false rozhodovacího bloku uvnitř těla funkce, kdy funkce volá sama sebe (svým jménem FaktorialRekurze) a předává si postupně snižovanou hodnotu parametru o jedna. Až se volaná funkce dostane do stavu, že daný parametr už nejde snížit (splnění podmínky ukončení další rekurze v těle funkce, tj. n == 0), funkce předá hodnotu 1 zpět do funkce, která ji naposledy volala. Pak tato volající metoda vypočte hodnotu svého výrazu a tuto hodnotu zase postupně dosazuje zpět do volající funkce. Tento cyklus probíhá tak dlouho, dokud neobdržíme výsledek příkazu, který odstartoval volání vnořených funkcí.

Použití rekurze je velmi účinný ale často také nebezpečný trik!