Récursivité en

À propos de Récursivité

On appelle récursivité la capacité d'une chose à se définir en termes d'elle-même. En F#, on rencontre le plus souvent la récursivité dans les fonctions récursives, c'est-à-dire des fonctions qui s'appellent elles-mêmes.

Une fonction récursive doit avoir au moins un cas de base et au moins un cas récursif. Un cas de base renvoie une valeur sans rappeler la fonction. Un cas récursif rappelle la fonction, en modifiant l'entrée pour qu'elle finisse par correspondre au cas de base.

Les fonctions récursives se définissent comme des fonctions habituelles, mais avec le modificateur rec. Sans ce modificateur, une fonction ne pourra pas s'appeler elle-même et toute tentative en ce sens provoquera une erreur de compilation. La récursivité doit donc être activée explicitement.

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

Les listes sont souvent traitées de manière récursive. Par exemple, voici comment utiliser la récursivité pour calculer la longueur d'une liste :

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

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

Bon nombre des fonctions intégrées sont définies de manière récursive.

Un problème possible avec les fonctions récursives est que chaque appel (récursif) provoque des allocations sur la pile, ce qui la fait croître. Comme la pile dispose d'une quantité limitée de mémoire, les fonctions qui font beaucoup d'appels récursifs peuvent provoquer le déclenchement d'une StackOverflowException. Le nombre d'appels récursifs nécessaire pour déclencher ce comportement dépend de plusieurs facteurs, comme la mémoire disponible sur la pile et la quantité de données que chaque appel de fonction y occupe.

La meilleure façon d'éviter que les fonctions récursives fassent déborder la pile est de les écrire comme des fonctions récursives terminales. Quand une fonction est récursive terminale, le compilateur peut optimiser sa sortie de sorte qu'il n'y ait plus d'allocations supplémentaires sur la pile à chaque appel récursif. La seule règle pour les fonctions récursives terminales est que le résultat d'un appel récursif doit être directement renvoyé par la fonction : il ne doit y avoir aucun code supplémentaire qui traite le résultat de l'appel récursif. La façon la plus courante de faire cela est de créer une fonction auxiliaire qui prend un argument accumulateur supplémentaire, mis à jour à chaque appel récursif et renvoyé lorsque la récursion se termine. Cette page détaille en profondeur la façon dont le compilateur traite les fonctions récursives terminales.

Voici une version récursive terminale de la fonction qui calcule la longueur d'une liste :

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

let length list = lengthRecursive 0 list

Il est assez courant de définir la fonction auxiliaire récursive comme une fonction imbriquée, ce qui cache la nature récursive de la fonction à l'appelant :

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

    lengthRecursive 0 list

F# prend en charge les types récursifs via les unions discriminées. Un type d'union discriminée récursif a un ou plusieurs de ses cas qui font référence au type d'union discriminée lui-même dans leurs données. Comme les fonctions récursives, les types récursifs doivent avoir un cas de base. Contrairement aux fonctions récursives, les types récursifs n'utilisent pas le mot-clé rec.

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

Voici une fonction (non récursive terminale) pour manipuler le type récursif ci-dessus :

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

layers (Layer Doll)
// => 1