Fonction récursive Elixir tail-call

Question

J'ai cette fonction qui trouve les nombres pairs dans une liste et renvoie une nouvelle liste avec seulement ces nombres :

  def even([]), do: []

  def even([head | tail]) when rem(head, 2) == 0 do
    [head | even(tail)]
  end

  def even([_head| tail]) do
    even(tail)
  end

Est-ce déjà optimisé pour les appels de queue ? Ou est-ce que chaque clause doit s'appeler elle-même à la fin (la deuxième version de la fonction "even" ne le fait pas) ? Si ce n'est pas le cas, comment peut-on la refactoriser pour qu'elle soit récursive par appel de queue ?

Je sais qu'il est possible de le faire avec un filtre ou une réduction, mais je voulais essayer sans cela.

Answer 1

Vous avez raison de dire que cette fonction n'est pas récursive parce que le dernier appel de la deuxième clause est l'opération de préparation de la liste, et non un appel à elle-même. Pour rendre cette fonction récursive à la queue, vous devrez utiliser un accumulateur. Puisque l'accumulation se fait en sens inverse, vous devrez inverser la liste dans la première clause.

def even(list), do: even(list, [])

def even([], acc), do: :lists.reverse(acc)

def even([head | tail], acc) when rem(head, 2) == 0 do
  even(tail, [head | acc])
end

def even([_head| tail], acc) do
  even(tail, acc)
end

Mais en Erlang, votre code "body-recursive" est automatiquement optimisé et peut ne pas être plus lent qu'une solution tail-recursive qui fait un :lists.reverse à la fin. La documentation d'Erlang recommande d'écrire celui des deux qui permet d'obtenir un code plus propre dans de tels cas.

Selon le mythe, l'utilisation d'une fonction récursive qui construit une liste à l'envers suivie d'un appel à lists:reverse/1 est plus rapide qu'une fonction récursive par corps qui construit la liste dans l'ordre correct ; la raison en est que les fonctions récursives par corps utilisent plus de mémoire que les fonctions récursives par queue.

Cela était vrai dans une certaine mesure avant la R12B. C'était encore plus vrai avant la R7B. Aujourd'hui, ce n'est plus vraiment le cas. Une fonction récursive utilise généralement la même quantité de mémoire qu'une fonction récursive. Il n'est généralement pas possible de prédire si la version récursive à la queue ou la version récursive au corps sera plus rapide. Par conséquent, utilisez la version qui rend votre code plus propre (indice : il s'agit généralement de la version récursive).

Pour une discussion plus approfondie sur la récursion de la queue et du corps, voir La récursion de la queue d'Erlang n'est pas une solution miracle .

Mythe : les fonctions récursives en queue sont beaucoup plus rapides que les fonctions récursives.