OCaml => Récursion de la queue

Introduction

Les langages fonctionnels tels que OCaml reposent largement sur des fonctions récursives . Toutefois, de telles fonctions peuvent entraîner une surconsommation de mémoire ou, lors de la manipulation de jeux de données volumineux, empiler des débordements .

La récursion de la queue est une source importante d'optimisation dans de tels cas. Il permet à un programme de supprimer le contexte de l'appelant lorsque l'appel récursif est le dernier de la fonction .

Fonction de somme

Vous trouverez ci-dessous une fonction non récursive pour calculer la somme d'une liste d'entiers.

let rec sum = function
  | [] -> 0
  | h::t -> h + (sum t)

La dernière opération effectuée par la fonction est l'addition. Ainsi, la fonction n'est pas récursive.

Vous trouverez ci-dessous une version récursive de la même fonction.

let sum l =
  let rec aux acc = function
    | [] -> acc
    | h::t -> aux (acc+h) t
  in
  aux 0 l

Ici, la fonction aux est récursive: la dernière opération effectuée est l'appelant. Par conséquent, cette dernière version de sum peut être utilisée avec des listes de n'importe quelle longueur.

Modified text is an extract of the original Stack Overflow Documentation

Sous licence CC BY-SA 3.0

Non affilié à Stack Overflow

OCaml
Récursion de la queue

Recherche…

Introduction

Fonction de somme