Partager via

Fonctions récursives : mot clé rec

  • Article

Le mot clé rec est utilisé avec le mot clé let pour définir une fonction récursive.

Syntaxe

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Notes

Les fonctions récursives - fonctions qui s’appellent elles-mêmes - sont identifiées explicitement dans le langage F# avec le mot clé rec. Le mot clé rec rend le nom de la liaison let disponible dans son corps.

L’exemple suivant montre une fonction récursive qui calcule le nième nombre Fibonacci à l’aide de la définition mathématique.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Notes

En pratique, un code comme l’échantillon précédent n’est pas idéal, car il recalcule inutilement des valeurs qui ont déjà été calculées. Cela est dû au fait qu’il n’est pas récursif terminal, ce qui est expliqué plus loin dans cet article.

Les méthodes sont implicitement récursives dans le type dans lequel elles sont définies, ce qui signifie qu’il n’est pas nécessaire d’ajouter le mot clé rec. Par exemple :

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

toutefois, les liaisons let au sein des classes ne sont pas implicitement récursives. Toutes les fonctions let liées nécessitent le mot clé rec.

Récursion terminale

Pour certaines fonctions récursives, il est nécessaire de refactoriser une définition plus « pure » en une définition récursive terminale. Cela évite les recalculs inutiles. Par exemple, le générateur de nombres Fibonacci précédent peut être réécrit comme suit :

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

La génération d’un nombre Fibonacci est un excellent exemple d’algorithme « naïf » qui est mathématiquement pur mais inefficace dans la pratique. Même s'il s'agit d’une implémentation plus complexe, plusieurs aspects la rendent efficace en F# tout en restant récursivement défini :

  • Fonction interne récursive nommée loop, qui est un modèle F# idiomatique.
  • Deux paramètres d’accumulateur, qui transmettent les valeurs accumulées aux appels récursifs.
  • Une vérification de la valeur de n pour retourner un accumulateur spécifique.

Si cet exemple était écrit itérativement avec une boucle, le code ressemblerait à deux valeurs différentes qui accumulent des nombres jusqu’à ce qu’une condition particulière soit remplie.

La raison pour laquelle il s’agit d’une récursive terminale est que l’appel récursif n’a pas besoin d’enregistrer de valeurs sur la pile des appels. Toutes les valeurs intermédiaires calculées sont accumulées par le biais d’entrées dans la fonction interne. Cela permet également au compilateur F# d’optimiser le code pour qu’il soit tout aussi rapide que si vous aviez écrit quelque chose comme une boucle while.

Il est courant d’écrire du code F# qui traite de manière récursive quelque chose avec une fonction interne et externe, comme l’illustre l’exemple précédent. La fonction interne utilise la récursivité terminale, tandis que la fonction externe a une meilleure interface pour les appelants.

À compter de F# 8.0, vous pouvez utiliser l’attribut TailCall pour indiquer explicitement au compilateur votre intention de définir une fonction récursive terminale. Le compilateur vous avertit ensuite si votre fonction effectue des appels récursifs non terminaux. Vous pouvez utiliser l’attribut sur les méthodes et les fonctions au niveau du module.
Par exemple, son utilisation sur la première définition de fib :

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

déclenche des avertissements du compilateur concernant les deux appels récursifs non terminaux.

Fonctions mutuellement récursives

Parfois, les fonctions sont mutuellement récursives, ce qui signifie que les appels forment un cercle, où une fonction appelle une autre qui appelle, à son tour, la première, avec un nombre quelconque d’appels entre eux. Vous devez définir ces fonctions ensemble dans une liaison let, en utilisant le mot clé and pour les lier ensemble.

L’exemple suivant montre deux fonctions mutuellement récursives.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Valeurs récursives

Vous pouvez également définir une valeur let liées pour qu’elle soit récursive. Ceci est parfois fait pour l’enregistrement. Avec F# 5 et la fonction nameof, vous pouvez procéder comme suit :

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Voir aussi