Pizzaárazás

Rekurzió

Rekurziónak nevezzük azt, amikor valami önmagára hivatkozva definiálható. Az F#-ban a rekurzió leggyakrabban rekurzív függvényekben fordul elő, amelyek önmagukat hívják.

Egy rekurzív függvénynek legalább egy alapesettel és legalább egy rekurzív esettel kell rendelkeznie. Az alapeset anélkül ad vissza egy értéket, hogy újra meghívná a függvényt. A rekurzív eset újra meghívja a függvényt, módosítva a bemenetet, hogy az előbb-utóbb megfeleljen az alapesetnek.

A rekurzív függvényeket ugyanúgy definiáljuk, mint a normál függvényeket, de a rec módosítóval. E módosító nélkül egy függvény nem tudja meghívni önmagát, és minden erre irányuló kísérlet fordítási hibát okoz. A rekurziót tehát explicit módon kell engedélyezni.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

Az F# a rekurzív típusokat is támogatja, méghozzá megkülönböztetett uniótípusok segítségével. Egy rekurzív megkülönböztetett uniótípus esetében egy vagy több eset adata magára az uniótípusra hivatkozik. A rekurzív függvényekhez hasonlóan a rekurzív típusoknak is legalább egy alapesettel kell rendelkezniük. A rekurzív függvényektől eltérően a rekurzív típusok nem használják a rec kulcsszót.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case