O que é recursão da cauda?

52

Eu conheço o conceito geral de recursão. Me deparei com o conceito de recursão da cauda enquanto estudava o algoritmo quicksort. Neste vídeo de algoritmo de ordenação rápida do MIT às 18:30 segundos, o professor diz que este é um algoritmo recursivo de cauda. Não está claro para mim o que realmente significa recursão da cauda.

Alguém pode explicar o conceito com um exemplo adequado?

Algumas respostas fornecidas pela comunidade SO aqui .

Nerd
fonte
Conte-nos mais sobre o contexto em que você encontrou o termo recursão de cauda . Ligação? Citação?
A.Schulz
@ A.Schulz Eu coloquei o link para o contexto.
22412 Geek
5
Veja " O que é recursão de cauda? " No stackoverflow
Vor
2
@ajmartin A questão é limítrofe no Stack Overflow, mas é firme no tópico sobre Ciência da Computação , portanto, em princípio, a Ciência da Computação deve produzir melhores respostas. Isso não aconteceu aqui, mas ainda é bom pedir novamente aqui na esperança de uma resposta melhor. Geek, você deveria ter mencionado sua pergunta anterior no SO, para que as pessoas não repitam o que já foi dito.
Gilles 'SO- stop be evil'
11
Além disso, você deve dizer o que é parte ambígua ou por que não está satisfeito com as respostas anteriores. Acho que as pessoas fornecem boas respostas, mas o que fez você perguntar novamente?

Respostas:

52

A recursão de cauda é um caso especial de recursão em que a função de chamada não faz mais cálculos depois de fazer uma chamada recursiva. Por exemplo, a função

int f (int x, int y) {
  se (y == 0) {
    retornar x;
  }

  retornar f (x * y, y-1);
}

é recursivo de cauda (já que a instrução final é uma chamada recursiva), enquanto esta função não é recursiva de cauda:

int g (int x) {
  if (x == 1) {
    retornar 1;
  }

  int y = g (x-1);

  retornar x * y;
}

já que faz algum cálculo após o retorno da chamada recursiva.

A recursão da cauda é importante porque pode ser implementada com mais eficiência do que a recursão geral. Quando fazemos uma chamada recursiva normal, precisamos inserir o endereço de retorno na pilha de chamadas e pular para a função chamada. Isso significa que precisamos de uma pilha de chamadas cujo tamanho seja linear na profundidade das chamadas recursivas. Quando temos recursão de cauda, ​​sabemos que, assim que retornarmos da chamada recursiva, retornaremos imediatamente também, para que possamos pular toda a cadeia de funções recursivas retornando e retornando diretamente para o chamador original. Isso significa que não precisamos de uma pilha de chamadas para todas as chamadas recursivas e podemos implementar a chamada final como um simples salto, o que economiza espaço.

Matt Lewis
fonte
2
você escreveu "Isso significa que não precisamos de uma pilha de chamadas para todas as chamadas recursivas". A pilha de chamadas sempre estará lá, apenas para que o endereço de retorno não precise ser gravado na pilha de chamadas, certo?
8773 Geek
2
Depende do seu modelo de computação até certo ponto :) Mas sim, em um computador real, a pilha de chamadas ainda está lá, simplesmente não a estamos usando.
Matt Lewis
E se for a chamada final, mas for for loop. Então você faz todos os seus cálculos acima, mas alguns deles em um loop comodef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
thed0ctor
13

Dito de forma simples, a recursão da cauda é uma recursão em que o compilador pode substituir a chamada recursiva por um comando "goto", para que a versão compilada não precise aumentar a profundidade da pilha.

Às vezes, projetar uma função recursiva de cauda exige que você precise criar uma função auxiliar com parâmetros adicionais.

Por exemplo, esta não é uma função recursiva da cauda:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

Mas esta é uma função recursiva da cauda:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

porque o compilador pode reescrever a função recursiva para uma função não recursiva, usando algo como isto (um pseudocódigo):

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

A regra para o compilador é muito simples: quando você encontrar " return thisfunction(newparameters);", substitua-o por " parameters = newparameters; goto start;". Mas isso pode ser feito apenas se o valor retornado pela chamada recursiva for retornado diretamente.

Se todas as chamadas recursivas em uma função puderem ser substituídas assim, é uma função recursiva de cauda.

Viliam Búr
fonte
13

Minha resposta é baseada na explicação dada no livro Estrutura e Interpretação de Programas de Computador . Eu recomendo este livro para cientistas da computação.

Abordagem A: Processo Recursivo Linear

(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

A forma do processo para a Abordagem A é assim:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Abordagem B: Processo Iterativo Linear

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

A forma do processo para a Abordagem B é assim:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

O processo iterativo linear (abordagem B) é executado em espaço constante, mesmo que o processo seja um procedimento recursivo. Também deve ser observado que, nesta abordagem, um conjunto de variáveis ​​define o estado do processo em qualquer ponto viz. {product, counter, max-count}. Essa também é uma técnica pela qual a recursão da cauda permite a otimização do compilador.

Na Abordagem A, há mais informações ocultas mantidas pelo intérprete, que são basicamente a cadeia de operações diferidas.

ajmartin
fonte
5

A recursão de cauda é uma forma de recursão na qual as chamadas recursivas são as últimas instruções na função (é daí que a parte da cauda vem). Além disso, a chamada recursiva não deve ser composta com referências a células de memória que armazenam valores anteriores (referências diferentes dos parâmetros da função). Dessa forma, não nos importamos com valores anteriores e um quadro de pilha é suficiente para todas as chamadas recursivas; recursão de cauda é uma maneira de otimizar algoritmos recursivos. A outra vantagem / otimização é que existe uma maneira fácil de transformar um algoritmo recursivo de cauda em um algoritmo equivalente que usa iteração em vez de recursão. Então, sim, o algoritmo do quicksort é realmente recursivo da cauda.

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Aqui está a versão iterativa:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1
saadtaame
fonte