Fonctions récursives : mot clé rec

Le rec mot clé est utilisé avec le let mot clé 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
...

Remarques

Les fonctions récursives - fonctions qui s’appellent - sont identifiées explicitement dans le langage F# avec le rec mot clé. Le rec mot clé rend le nom de la let liaison 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)

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 rec mot clé. Par exemple:

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

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

Récursivité de la queue

Pour certaines fonctions récursives, il est nécessaire de refactoriser une définition plus « pure » à une définition de queue récursive. Cela empêche les recomputations 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ïve » qui est mathématiquement pur mais inefficace dans la pratique. Bien qu’il s’agit d’une implémentation plus complexe, plusieurs aspects le 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’accumulation, qui transmettent des valeurs accumulées aux appels récursifs.
• Contrôle de la valeur de retour d’un n accumulateur spécifique.

Si cet exemple a été écrit itérativement avec une boucle, le code ressemble à 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 queue récursive est parce 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 d’être aussi rapide que si vous aviez écrit quelque chose comme une while boucle.

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é de la queue, 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 votre intention de définir une fonction tail-recursive au compilateur. Le compilateur vous avertit ensuite si votre fonction effectue des appels récursifs non-tail. Vous pouvez utiliser l’attribut sur les méthodes et les fonctions au niveau du module.
Par exemple, en l’utilisant sur la première fib définition :

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

déclencherait des avertissements du compilateur concernant les deux appels récursifs non tail.

Fonctions récursives mutuelles

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

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

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 letvaleur -bound pour être récursive. Cela est parfois fait pour la journalisation. Avec F# 5 et la nameof fonction, vous pouvez procéder comme suit :

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Voir aussi

• Fonctions