queue appeler la fonction récursive

Question

Je trouve cette fonction que les nombres pairs dans une liste et retourne une nouvelle liste avec seulement ces chiffres:

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à la queue appel optimisé? Ou est-ce que chaque clause doit s'appeler à la fin (la deuxième version de la fonction "paire" ne le fait pas)? Si non, comment peut-il être refacturé pour être récursif? Je sais que cela peut être fait avec un filtre ou réduire mais je voulais essayer sans cela.

Answer 1

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

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 « corps-récursive » est automatiquement optimisée et ne peut être plus lente qu'une solution récurrente-queue qui fait un appel :lists.reverse à la fin. La documentation d'Erlang recommande d'écrire l'un ou l'autre des deux résultats dans un code plus propre dans de tels cas.

Selon la légende, en utilisant une fonction récursive qui construit une liste dans le sens inverse suivi d'un appel à lists:reverse/1 est plus rapide que la fonction de corps récursif qui construit la liste dans l'ordre correct; la raison en est que les fonctions récursives utilisent plus de mémoire que les fonctions récursives.

Cela était vrai dans une certaine mesure avant R12B. C'était encore plus vrai avant R7B. Aujourd'hui, pas tellement. 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 de la queue ou la version récursive du 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 body-récursive).

Pour une discussion plus approfondie sur la récursivité de la queue et du corps, voir Erlang's Tail Recursion is Not a Silver Bullet.

Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions.