Rekurzió ebben a kurzusban:

A(z) Rekurzió fogalomról

Azt a képességet, hogy valamit önmagával definiálunk, rekurziónak nevezzük. Az F#-ban a rekurzió leggyakrabban rekurzív függvényekben fordul elő, vagyis olyan függvényekben, amelyek önmagukat hívják meg.

Egy rekurzív függvényben legalább egy alapesetnek és legalább egy rekurzív esetnek kell lennie. Az alapeset úgy ad vissza egy értéket, hogy nem hívja meg újra a függvényt. A rekurzív eset újra meghívja a függvényt, és úgy módosítja a bemenetet, hogy az előbb-utóbb illeszkedjen az alapesethez.

A rekurzív függvényeket ugyanúgy definiáljuk, mint a hagyományos függvényeket, csak a rec módosítóval. A módosító nélkül egy függvény nem tudja meghívni önmagát, és minden ilyen próbálkozás fordítási hibát eredményez. A rekurziót tehát kifejezetten választani kell.

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

A listákat gyakran rekurzívan dolgozzuk fel. Íme egy példa arra, hogyan számoljuk ki rekurzióval egy lista hosszát:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

A beépített függvények közül sok rekurzívan van definiálva.

A rekurzív függvények egyik lehetséges problémája, hogy minden (rekurzív) függvényhívás foglalást eredményez a vermen, ami annak növekedését okozza. Mivel a verem memóriája korlátozott, a sok rekurzív hívást használó függvények StackOverflowException kivételt dobhatnak. Az, hogy hány rekurzív hívás váltja ki ezt a viselkedést, több tényezőtől függ, például a rendelkezésre álló veremmemóriától és attól, hogy az egyes függvényhívások mennyi adatot foglalnak el a vermen.

A legjobb módja annak, hogy megakadályozzuk a rekurzív függvények veremtúlcsordulását, ha farokrekurzív függvényként írjuk meg őket. Amikor egy függvény farokrekurzív, a fordító úgy optimalizálhatja a kimenetét, hogy minden rekurzív függvényhívásnál ne történjen további foglalás a vermen. A farokrekurzív függvények egyetlen szabálya, hogy a rekurzív függvényhívás eredményét közvetlenül kell visszaadni a függvényből, nem lehet olyan további kód, amely feldolgozza a rekurzív hívás eredményét. A leggyakoribb megoldás erre egy segédfüggvény létrehozása, amely egy további akkumulátor argumentumot kap, amelyet minden rekurzív hívásnál frissítünk, és amikor a rekurzió véget ér, visszaadunk. Ez az oldal nagy részletességgel tárgyalja, hogyan dolgozza fel a fordító a farokrekurzív függvényeket.

Íme a listahossz-függvény farokrekurzív változata:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

Gyakori, hogy a rekurzív segédfüggvényt egymásba ágyazott függvényként definiáljuk, ami elrejti a függvény rekurzív természetét a hívó elől:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

Az F# diszkriminált unió típusokon keresztül támogatja a rekurzív típusokat. Egy rekurzív diszkriminált unió típusnak egy vagy több esete az adataiban magára a diszkriminált unió típusra hivatkozik. A rekurzív függvényekhez hasonlóan a rekurzív típusoknak is kell alapesetük. A rekurzív függvényekkel ellentétben a rekurzív típusok nem használják a rec kulcsszót.

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

Íme egy (nem farokrekurzív) függvény, amely a fenti rekurzív típussal dolgozik:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1