Qual é a vantagem de usar a recursão de cauda aqui?

Question 1

Uma chamada de função recursiva final permite que o compilador execute uma otimização especial que normalmente não consegue com a recursão regular.Em uma função recursiva final, a chamada recursiva é a última coisa a ser executada.Nesse caso, em vez de alocar um quadro de pilha para cada chamada, o compilador pode retrabalhar o código para simplesmente reutilizar o quadro de pilha atual, o que significa que uma função recursiva final usará apenas um único quadro de pilha em vez de centenas ou mesmo milhares.

Essa otimização é possível porque o compilador sabe que uma vez feita a chamada recursiva final, nenhuma cópia anterior das variáveis será necessária, pois não há mais código para executar.Se, por exemplo, uma instrução print seguisse uma chamada recursiva, o compilador precisaria saber o valor da variável a ser impressa após o retorno da chamada recursiva e, portanto, o quadro da pilha não poderia ser reutilizado.

Aqui está a página wiki se você quiser mais informações sobre como essa "economia de espaço" e reutilização de pilha realmente funciona, junto com exemplos: Chamada final

Editar:Não expliquei como isso se aplica ao quicksort, não é?Bem, alguns termos são usados nesse artigo que tornam tudo confuso (e alguns deles são simplesmente errados).A primeira função fornecida (QUICKSORT) faz uma chamada recursiva à esquerda, uma chamada recursiva à direita e depois sai.Observe que a chamada recursiva à direita é a última coisa que acontece na função.Se o compilador suportar otimização recursiva final (explicada acima), apenas as chamadas à esquerda criarão novos quadros de pilha;todas as chamadas certas apenas reutilizam o quadro atual.Isso pode salvar alguns stack frames, mas ainda pode sofrer no caso em que o particionamento cria uma sequência de chamadas onde a otimização da recursão final não importa.Além disso, embora as chamadas do lado direito usem o mesmo quadro, as chamadas do lado esquerdo chamadas dentro de as chamadas do lado direito ainda usam a pilha.Na pior das hipóteses, a profundidade da pilha é N.

A segunda versão descrita é não um quicksort recursivo de cauda, mas sim um quicksort onde apenas a classificação à esquerda é feita recursivamente e a classificação à direita é feita usando o loop.Na verdade, esse quicksort (conforme descrito anteriormente por outro usuário) não pode ter a otimização de recursão final aplicada a ele, porque a chamada recursiva não é a última coisa a ser executada.Como é que isso funciona?Quando implementada corretamente, a primeira chamada para quicksort é igual à chamada do lado esquerdo no algoritmo original.No entanto, nenhuma chamada recursiva do lado direito é chamada.Como é que isso funciona?Bem, o loop cuida disso:em vez de classificar "esquerda e direita", ele classifica a esquerda com uma chamada e, em seguida, classifica a direita classificando continuamente apenas os esquerdas da direita.Parece realmente ridículo, mas basicamente é apenas classificar tantas esquerdas que as direitas se tornam elementos únicos e não precisam ser classificadas.Isso efetivamente remove a recursão correta, tornando a função menos recursiva (pseudo recursiva, se preferir).Contudo, a implementação real não escolhe apenas o lado esquerdo de cada vez;ele escolhe o menor lado.A ideia ainda é a mesma;basicamente faz apenas uma chamada recursiva de um lado em vez de ambos.Escolher o lado mais curto garantirá que a profundidade da pilha nunca possa ser maior que log2(N), que é a profundidade de uma árvore binária adequada.Isso ocorre porque o lado mais curto sempre terá no máximo metade do tamanho da seção atual do array.A implementação dada pelo artigo não garante isso, pois pode sofrer do mesmo pior cenário de "a esquerda é a árvore inteira".Na verdade, este artigo fornece uma boa explicação sobre isso, se você estiver disposto a ler mais: Seleção eficiente e classificação parcial baseada em quicksort

Question 2

A vantagem, todo o ponto da versão "mista recursiva/iterativa", ou seja,versão que processa um subintervalo por recursão e outro subintervalo por iteração, é que ao escolher qual dos dois subintervalos processar recursivamente você pode garantir que a profundidade da recursão nunca excederá log2 N, independentemente de quão ruim seja a escolha do pivô.

Para o TAIL-RECURSIVE-QUICKSORT pseudocódigo fornecido na pergunta, onde o processamento recursivo é executado primeiro por uma chamada recursiva literal, essa chamada recursiva deve receber o mais curta subfaixa.Isso por si só garantirá que a profundidade da recursão será limitada por log2 N.Portanto, para atingir a garantia de profundidade de recursão, o código precisa absolutamente comparar os comprimentos dos subintervalos antes de decidir qual subintervalo processar por chamada recursiva.

Uma implementação adequada dessa abordagem pode ser a seguinte (pegando emprestado seu pseudocódigo como ponto de partida)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

O TAIL-RECURSIVE-QUICKSORT o pseudocódigo que você forneceu não faz nenhuma tentativa de comparar os comprimentos dos subintervalos.Nesse caso, não traz nenhum benefício.E não, não é realmente "cauda recursiva".O QuickSort não pode ser reduzido a um algoritmo recursivo de cauda.

Se você fizer uma pesquisa no Google sobre os termos "qsort loguy higuy", encontrará facilmente inúmeras instâncias de outra implementação popular do QuickSort (estilo de biblioteca padrão C) baseada na mesma ideia de usar recursão para apenas um dos dois subintervalos .Essa implementação para plataformas de 32 bits usa pilha explícita de profundidade máxima de ~32, especificamente porque pode garantir que a profundidade de recursão nunca será maior que isso.(Da mesma forma, as plataformas de 64 bits precisarão apenas de uma profundidade de pilha de aproximadamente 64.)

O QUICKSORT A versão que faz duas chamadas recursivas literais é significativamente pior nesse aspecto, uma vez que a má escolha repetitiva do pivô pode fazer com que ele atinja uma profundidade de recursão muito alta, até N na pior das hipóteses.Com duas chamadas recursivas você não pode garantir que a profundidade da recursão será limitada por log2 N.Um compilador inteligente pode substituir a chamada final para QUICKSORT com iteração, ou seja,vire seu QUICKSORT dentro de voce TAIL-RECURSIVE-QUICKSORT, mas não será inteligente o suficiente para realizar a comparação do comprimento do subintervalo.

Question 3

Vantagem de usar tail-recursion := para que o compilador otimize o código e o converta em um código não recursivo.

Vantagem do código não recursivo sobre o recursivo: = o código não recursivo requer menos memória para ser executado do que um código recursivo.Isso ocorre por causa dos quadros de pilha ociosos que a recursão consome.

Aí vem a parte interessante: - mesmo que os compiladores pode teoricamente realizam essa otimização, na prática não.mesmo os compiladores difundidos como dot-net e java não realizam essa otimização.

um problema que todas as otimizações de código enfrentam é o sacrifício da capacidade de depuração.o código otimizado não corresponde mais ao código-fonte, portanto, os rastreamentos de pilha e os detalhes das exceções não podem ser facilmente compreendidos.código de alto desempenho ou aplicativos científicos são uma coisa, mas para a maioria dos aplicativos de consumo a depuração é necessária mesmo após o lançamento.portanto, as otimizações não são feitas com tanto vigor.

por favor, veja:

Question 4

Parece haver alguma confusão de vocabulário aqui.

A primeira versão é recursiva, porque a última instrução é uma chamada recursiva:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

Se você aplicar a otimização de recursão final, que consiste em converter a recursão em um loop, você obterá a segunda, que não é mais recursiva final:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

A vantagem disso é que normalmente você precisará de menos memória de pilha.Por que é que?Para entender, imagine que você deseja ordenar um array com 31 itens.No caso altamente improvável de que todas as partições sejam perfeitas, ou seja,eles dividiram o array bem no meio, sua profundidade de recursão seria 4.Na verdade, a primeira divisão produziria duas partições de 15 itens, a segunda duas partições de 7 itens, a terceira duas de 3 itens e depois da quarta tudo estaria classificado.

Mas as partições raramente são tão perfeitas.Como resultado, nem todas as recursões são igualmente profundas.Em nosso exemplo, você pode ter alguns com apenas três níveis de profundidade e outros com 7 ou mais (o pior caso é 30).Ao eliminar metade das recursões, você tem uma boa chance de que a profundidade máxima da recursão seja menor.

Como AndreyT apontou, muitas vezes os intervalos são comparados para garantir que a maior partição seja sempre processada iterativamente e a menor recursivamente.Isso garante a menor profundidade de recursão possível para uma determinada estratégia de seleção de entrada e pivô.

Mas nem sempre é esse o caso.Às vezes, as pessoas desejam produzir resultados o mais rápido possível ou desejam encontrar e classificar apenas os primeiros n elementos.Nestes casos eles sempre querem ordenar a primeira partição antes da segunda.Mesmo nessa situação, eliminar a recursão final geralmente melhora o uso da memória e nunca piora.

Question 5

Não sei exatamente se este é o lugar correto para tirar essa dúvida ou deveria ter postado uma nova pergunta mas tenho uma dúvida bastante parecida.



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

Essa cauda é recursiva?

Question 6

A recursão final é a otimização feita por compiladores modernos chamada eliminação de chamada final.Quando a função chamador/pai não precisa fazer nada nos estágios de desenrolamento após o término das chamadas filhas, a última coisa é a própria chamada de recursão, então o compilador moderno usa goto e rótulos para a otimização.

exemplo:Nossa versão -> Imprime n em 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

após otimização->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Vantagens desta otimização:1. Usina muito poucos quadros de pilha para chamadas Recursivas para a cauda 2. Consuma menos memória 3. Não é necessário salvar o registro de ativação do procedimento, isso reduz a sobrecarga da função.3. Não há mais falha de segmentação em C/C++ e estouro de pilha em java.