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 comporter 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.

Très souvent, chaque cas est écrit dans sa propre clause de fonction.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

Une fonction récursive peut comporter plusieurs cas de base et/ou plusieurs cas récursifs. Par exemple, la suite de Fibonacci est une suite récursive avec deux cas de base :

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Compter le nombre d'occurrences d'une valeur donnée x dans un tableau comporte deux cas récursifs :

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Les boucles grâce à la récursion

En raison de l'immuabilité, les boucles en Elixir s'écrivent différemment de celles des langages impératifs. Par exemple, une boucle ressemble souvent à ceci :

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

Dans un langage fonctionnel, il n'est pas possible de modifier i (en appelant i++). Les boucles doivent donc être implémentées avec de la récursion.

L'équivalent d'une boucle for en Elixir ressemblerait à ceci :

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

En pratique, on parcourt le plus souvent des tableaux et d'autres structures de données énumérables à l'aide du module Enum. Sous le capot, les fonctions du module Enum sont implémentées à l'aide de la récursion.

L'exécution infinie

Si elles sont mal implémentées, les fonctions récursives peuvent ne jamais renvoyer leur résultat. Cela peut poser problème, car à chaque appel de 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 venir à manquer et faire planter la VM (une erreur de débordement de pile). La VM Erlang, sur laquelle Elixir s'exécute, est spécialement optimisée pour la récursion et la fiabilité, il peut donc s'écouler beaucoup de temps avant que les erreurs de récursion infinie ne se manifestent ou qu'un plantage ne survienne.

Ce problème d'exécution infinie peut être causé par :

• 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.