Silnia - rekurencyjny algorytm

Rekurencję poznaje się tak naprawdę już w szkole średniej podczas liczenia silniej. Niestety ten sposób liczenia dla człowieka jest raczej uciążliwy, ale za to dla komputera wręcz idealny. W kodzie napisanym przez Sundaya możemy spotkać wywołującą się samą funkcję dzięki której liczymy wartość silniej. Jak zwykle oddaje głos specjaliście od kodowania, który tym razem przygotował wstęp teoretyczny. Sunday, do dzieła!

Procek

Silnia... Na matematyce poznaje się ją przy kombinatoryce, a na informatyce przy algorytmice. Silnia - to funkcja oznaczana symbolem "!" i definiowana jako:

n!=1*2*3*4*...(n-2)*(n-1)*n dla n>0 i 0!=1

Rekurencyjny wzór silniej

0!=1;

n!=(n-1)!*n dla n>0

Myślę że każdy rozumie te wzory(jak nie to polecam powrót do liceum). W informatyce silnię z reguły obliczmy za pomocą drugiego ze wzorów - wzoru rekurencyjnego, jest to szybsze, wydajniejsze i łatwiejsze w implemtentacji. Oto funkcje liczące silnię z podanej liczby, będące bezpośrednim "tłumaczeniem" języka matematyki na język programowania.

Prezentacja algorytmu na przykładzie języka C++

unsigned Silnia(unsigned liczba) //To jest funkcja o nazwie Silnia, ma pobierać argument "liczba" który jest liczbą naturalną, i zwracać wartość która też jest liczbą naturalną
{
if(liczba==0){return 1;} //Jeżeli liczymy silnię 0 to jest to 1 (Z definicji rekurencyjnej silni 0!=1)
else return Silnia(liczba-1)*liczba; //Jeżeli nie liczymy slini 0 to policzymy silnię dla argumentu mniejszego o 1 od obecnego i pomnożymy go przez obecny argument(Z definicji rekurencyjnej silni n!=(n-1)!*n)
}

Implementacja w języku Pascal

function Silnia(liczba:word):word; //To jest funkcja o nazwie Silnia, ma pobierać argument 'liczba' który jest liczbą naturalną, i zwracać wartość która też jest liczbą naturalną
begin
if liczba=0 then Silnia:=1 //Jeżeli liczymy silnię 0 to jest to 1(Z definicji rekurencyjnej silni 0!=1)
else Silnia:=Silnia(liczba-1)*liczba; //Jeżeli nie liczymy slini 0 to policzymy silnię dla argumentu mniejszego o 1 od obecnego i pomnożymy go przez obecny argument(Z definicji rekurencyjnej silni n!=(n-1)!*n)
end;

Sunday