Récursivité en

À propos de Récursivité

Les fonctions récursives sont des fonctions qui s'appellent elles-mêmes.

Une fonction récursive doit posséder 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.

Voici un exemple qui compte les éléments d'un tableau.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

Une fonction récursive peut avoir plusieurs cas de base et/ou plusieurs cas récursifs. Par exemple, la suite de Fibonacci est une suite récursive qui possède deux cas de base.

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

Compter le nombre d'occurrences d'une valeur donnée x dans un tableau fait intervenir deux cas récursifs.

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

En pratique, on parcourt le plus souvent les tableaux et les autres structures de données énumérables à l'aide de fonctions intégrées, comme map et reduce, ou en utilisant les flux comme [.[] | select(...)]. Sous le capot, certaines fonctions intégrées sont implémentées à l'aide de la récursion.

La récursion infinie

Mal implémentées, les fonctions récursives peuvent ne jamais renvoyer leur résultat. Cela peut poser problème, car à chaque appel d'une fonction, une référence est stockée en mémoire à l'endroit où la VM doit renvoyer le résultat (sur la pile d'appels). Si une fonction récursive s'appelle elle-même à l'infini, la mémoire peut finir par manquer, ce qui fait planter la VM avec une erreur de dépassement de pile.

Ce problème de récursion infinie peut avoir plusieurs causes :

• Oublier d'implémenter un cas de base.
• Ne pas définir le cas de base comme première clause.
• Ne pas modifier correctement l'argument lors de l'appel récursif, et donc ne jamais atteindre le cas de base.

Optimisation des appels terminaux

Comme décrit sur Wikipédia :

Un appel terminal est un appel de sous-programme effectué comme dernière action d'une procédure. Si la cible d'un appel terminal est le même sous-programme, on dit que le sous-programme est récursif terminal.

Considérons l'implémentation de fibonacci donnée plus haut. Le cas récursif s'appelle lui-même deux fois. La dernière action que la fonction doit effectuer est une addition. Comme cette dernière action n'est pas un appel à elle-même, la fonction est récursive, mais pas récursive terminale.

Certains langages implémentent l'optimisation des appels terminaux, ce qui permet à l'appel terminal de réutiliser la frame de pile courante au lieu d'ajouter une nouvelle frame à la pile d'appels. En plus de protéger contre le redouté dépassement de pile, cela peut améliorer les performances.

jq implémente bien l'optimisation des appels terminaux, mais uniquement pour les fonctions d'arité 0. Pour en tirer parti, on définit une fonction « interne » d'arité 0 qui prend un certain état en entrée. La fonction interne peut modifier l'état selon les besoins et transmettre le nouvel état à l'appel récursif terminal. La fonction externe crée l'état initial et le transmet à la fonction interne pour démarrer la récursion.

On peut implémenter une fonction fibonacci récursive terminale en conservant la série calculée jusqu'ici comme partie de l'état.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55