Diferencia entre la recursividad de cola y la recursividad estructural

¿Hay alguna diferencia entre la recursividad estructural y la recursividad de cola o ambas son iguales? Veo que en estas dos recursiones, la función recursiva se llama en el subconjunto de los elementos originales.

1. Recurrencia estructural: las llamadas recursivas se realizan sobre argumentos estructuralmente más pequeños .

2. Recurrencia de la cola: la llamada recursiva es lo último que sucede.

No hay ningún requisito de que la recursión de cola se invoque en un argumento más pequeño. De hecho, con bastante frecuencia las funciones recursivas de cola están diseñadas para repetirse para siempre. Por ejemplo, aquí hay una recursión trivial de la cola (no muy útil, pero es una recursión de la cola):

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

De hecho, tenemos que ser un poco más cuidadosos. Puede haber varias llamadas recursivas en una función, y no todas deben ser recursivas de cola:

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

Se habla de llamadas recursivas de cola . Una función recursiva cuyas llamadas son todos recursiva de cola se llama entonces una función recursiva de cola.

La recursividad de cola es un caso muy simple de recursión estructural, donde la estructura en cuestión es una lista vinculada . En el lenguaje que probablemente esté utilizando principalmente, esta lista probablemente no esté literalmente en el código; más bien, es una "lista de llamadas a la función" conceptual, un concepto que puede no ser posible expresar como está escrito usando ese lenguaje. En Haskell (mi lenguaje), cualquier llamada de función recursiva de cola puede reemplazarse por acciones secuenciales en una lista literal cuyos elementos son literalmente "llamadas a una función", pero esto es probablemente una cuestión de lenguaje funcional.

La recursividad estructural es una forma de operar en un objeto definido como un compuesto de otros objetos (posiblemente compuestos). Por ejemplo, un árbol binario es un objeto que contiene referencias a dos árboles binarios, o está vacío (por lo tanto, es un objeto definido recursivamente ). Menos autorreferencialmente, un par (t1, t2) que contiene dos valores de algunos tipos t1 y t2 admite recursividad estructural, aunque t1 y t2 no necesitan ser también pares. Esta recursión toma la forma

acción en el par = combinación de los resultados de otras acciones en cada elemento

lo cual no suena muy profundo.

A menudo se da el caso de que una recursión estructural no puede ser recursiva de la cola, aunque cualquier tipo de recursión puede reescribirse como una recursión de cola (prueba: si ejecuta la recursión original, las acciones se completan en un cierto orden; por lo tanto, la recursividad es equivalente a realizar esa secuencia particular de acciones, que como mencioné anteriormente, es la recursión de cola).

El árbol binario o el ejemplo de par anterior lo demuestran: sin embargo, si organiza las llamadas recursivas en los subobjetos, solo uno de ellos puede ser la última acción; posiblemente ninguno lo es, si sus resultados se combinan de alguna manera (digamos, suma). Como Andrej Bauer dice en su respuesta, esto puede suceder incluso con una sola llamada recursiva, siempre que se modifique el resultado. En otras palabras, para cada tipo de objeto que no sean los que están efectivamente vinculados listas (solo un subobjeto hasta el final), la recursión estructural no es la recursividad de cola.