Diferença entre recursão de cauda e recursão estrutural

Existe alguma diferença entre recursão estrutural e recursão de cauda ou ambos são iguais? Vejo que, nessas duas recursões, a função recursiva é chamada no subconjunto dos itens orignais.

1. Recursão estrutural: chamadas recursivas são feitas em argumentos estruturalmente menores .

2. Recursão de cauda: a chamada recursiva é a última coisa que acontece.

Não há exigência de que a recursão da cauda deva ser chamada em um argumento menor. De fato, muitas vezes as funções recursivas da cauda são projetadas para repetir para sempre. Por exemplo, aqui está uma recursão trivial da cauda (não muito útil, mas é uma recursão da cauda):

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

Na verdade, temos que ter um pouco mais de cuidado. Pode haver várias chamadas recursivas em uma função e nem todas elas precisam ser recursivas de cauda:

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

Fala-se de chamadas recursivas de cauda . Uma função cujas chamadas recursivas são todas recursivas na cauda é chamada de função recursiva na cauda.

A recursão da cauda é um caso muito simples de recursão estrutural, em que a estrutura em questão é uma lista vinculada . No idioma que você provavelmente está usando principalmente, esta lista provavelmente não está literalmente no código; pelo contrário, é uma "lista de chamadas para a função" conceitual, um conceito que pode não ser possível expressar como escrito usando essa linguagem. Em Haskell (minha linguagem), qualquer chamada de função recursiva de cauda pode realmente ser substituída por ações de seqüenciamento em uma lista literal cujos elementos são literalmente "chamadas para uma função", mas isso provavelmente é uma coisa da linguagem funcional.

A recursão estrutural é uma maneira de operar em um objeto definido como um composto de outros objetos (possivelmente compostos). Por exemplo, uma árvore binária é um objeto que contém referências a duas árvores binárias ou está vazio (portanto, é um objeto definido recursivamente ). Menos auto-referencialmente, um par (t1, t2) contendo dois valores de alguns tipos t1 e t2 admite recursão estrutural, embora t1 e t2 também não precisem ser pares. Essa recursão assume a forma

ação no par = combinação dos resultados de outras ações em cada elemento

o que não parece muito profundo.

Geralmente, uma recursão estrutural não pode ser recursiva de cauda, ​​embora qualquer tipo de recursão possa ser reescrita como recursão de cauda (prova: se você executar a recursão original, as ações serão concluídas em uma determinada ordem; portanto, a recursão é equivalente a executar essa sequência específica de ações, que, como discuti anteriormente, é recursão de cauda).

A árvore binária ou o exemplo de par acima demonstram isso: no entanto, você organiza as chamadas recursivas nos subobjetos, apenas uma delas pode ser a última ação; possivelmente nenhum deles seja, se seus resultados forem combinados de alguma maneira (digamos, adição). Como Andrej Bauer diz em sua resposta, isso pode acontecer mesmo com apenas uma chamada recursiva, desde que o resultado seja modificado. Em outras palavras, para todos os tipos de objetos que não sejam efetivamente listas vinculadas (apenas um subobjeto até o fim), a recursão estrutural não é recursiva final.