Différence entre la récursion de queue et la récursion structurelle

Y a-t-il une différence entre la récursion structurelle et la récursion de queue ou les deux sont-ils identiques? Je vois que dans ces deux récursions, la fonction récursive est appelée sur le sous-ensemble des éléments d'origine.

1. Récursion structurelle: des appels récursifs sont effectués sur des arguments structurellement plus petits .

2. Récursivité de la queue: l'appel récursif est la dernière chose qui se passe.

Il n'est pas nécessaire que la récursivité de queue soit appelée sur un argument plus petit. En fait, les fonctions récursives de queue sont souvent conçues pour boucler pour toujours. Par exemple, voici une récursion de queue triviale (pas très utile, mais c'est une récursion de queue):

def f(x):
   return f(x+1)

Nous devons en fait être un peu plus prudents. Il peut y avoir plusieurs appels récursifs dans une fonction, et tous n'ont pas besoin d'être récursifs de queue:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

On parle d' appels récursifs de queue . Une fonction dont les appels récursifs sont tous récursifs de queue est alors appelée fonction récursive de queue.

La récursivité de queue est un cas très simple de récursion structurelle, où la structure en question est une liste chaînée . Dans la langue que vous utilisez probablement principalement, cette liste n'est probablement pas littéralement dans le code; il s'agit plutôt d'une "liste d'appels à la fonction" conceptuelle, un concept qui peut ne pas être possible d'exprimer tel qu'il est écrit en utilisant ce langage. Dans Haskell (mon langage), tout appel de fonction récursif de queue peut en fait être remplacé par des actions de séquencement sur une liste littérale dont les éléments sont littéralement des "appels à une fonction", mais c'est probablement une chose de langage fonctionnel.

La récursion structurelle est une façon de fonctionner sur un objet défini comme un composite d'autres objets (éventuellement composites). Par exemple, un arbre binaire est un objet contenant des références à deux arbres binaires, ou est vide (il s'agit donc d'un objet défini récursivement ). Moins autoréférentiellement, une paire (t1, t2) contenant deux valeurs de certains types t1 et t2 admet une récursivité structurelle, bien que t1 et t2 n'aient pas besoin également d'être des paires. Cette récursivité prend la forme

action sur la paire = combinaison des résultats d'autres actions sur chaque élément

ce qui ne semble pas très profond.

Il arrive souvent qu'une récursion structurelle ne puisse pas être récursive de queue, bien que toute sorte de récursivité puisse être réécrite comme une récursion de queue (preuve: si vous exécutez la récursivité d'origine, les actions sont terminées dans un certain ordre; par conséquent, la récursivité équivaut à effectuer cette séquence particulière d’actions, qui, comme je l’ai expliqué plus haut, est la récursivité de la queue).

L'arbre binaire ou l'exemple de paire ci-dessus le démontrent: quelle que soit l'organisation des appels récursifs sur les sous-objets, un seul d'entre eux peut être la dernière action; peut-être que ni l'un ni l'autre ne l'est, si leurs résultats sont combinés d'une certaine manière (disons, addition). Comme Andrej Bauer le dit dans sa réponse, cela peut se produire même avec un seul appel récursif, tant que le résultat est modifié. En d'autres termes, pour chaque type d'objet autre que ceux qui sont effectivement des listes liées (un seul sous-objet tout en bas), la récursivité structurelle n'est pas une récursion de queue.