O que é recursion da cauda?

Ao começar a aprender lisp, eu me deparei com o termo tail-recursivo . O que isso significa exatamente?

Considere uma function simples que adiciona os primeiros N inteiros. (por exemplo, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Aqui está uma implementação JavaScript simples que usa recursion:

 function recsum(x) { if (x===1) { return x; } else { return x + recsum(x-1); } } 

Se você chamou recsum(5) , isso é o que o interpretador JavaScript avaliaria:

 recsum(5) 5 + recsum(4) 5 + (4 + recsum(3)) 5 + (4 + (3 + recsum(2))) 5 + (4 + (3 + (2 + recsum(1)))) 5 + (4 + (3 + (2 + 1))) 15 

Observe como cada chamada recursiva deve ser concluída antes que o interpretador JavaScript comece a fazer o trabalho de calcular a sum.

Aqui está uma versão recursiva da mesma function:

 function tailrecsum(x, running_total=0) { if (x===0) { return running_total; } else { return tailrecsum(x-1, running_total+x); } } 

Aqui está a seqüência de events que ocorreria se você chamasse tailrecsum(5) , (que seria efetivamente tailrecsum(5, 0) , por causa do segundo argumento padrão).

 tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15 

No caso recursivo da cauda, ​​a cada avaliação da chamada recursiva, o running_total é atualizado.

Nota: A resposta original usou exemplos do Python. Estes foram alterados para JavaScript, já que os intérpretes JavaScript modernos suportam a otimização da chamada final, mas os intérpretes do Python não.

Na recursion tradicional , o modelo típico é que você executa suas chamadas recursivas primeiro e depois pega o valor de retorno da chamada recursiva e calcula o resultado. Dessa maneira, você não obtém o resultado do seu cálculo até retornar de todas as chamadas recursivas.

Na recursion final , você executa seus cálculos primeiro e, em seguida, executa a chamada recursiva, passando os resultados de sua etapa atual para a próxima etapa recursiva. Isso resulta na última declaração na forma de (return (recursive-function params)) . Basicamente, o valor de retorno de qualquer etapa recursiva é o mesmo que o valor de retorno da próxima chamada recursiva .

A conseqüência disso é que, quando você estiver pronto para executar sua próxima etapa recursiva, você não precisará mais do quadro de pilha atual. Isso permite alguma otimização. Na verdade, com um compilador adequadamente escrito, você nunca deve ter um snicker de estouro de pilha com uma chamada recursiva de cauda. Simplesmente reutilize o quadro de pilha atual para a próxima etapa recursiva. Tenho certeza que Lisp faz isso.

Um ponto importante é que a recursion da cauda é essencialmente equivalente ao looping. Não é apenas uma questão de otimização do compilador, mas um fato fundamental sobre expressividade. Isso vai nos dois sentidos: você pode pegar qualquer loop do formulário

 while(E) { S }; return Q 

onde E e Q são expressões e S é uma seqüência de instruções, e transformá-lo em uma function recursiva final

 f() = if E then { S; return f() } else { return Q } 

Obviamente, E , S e Q precisam ser definidos para computar algum valor interessante sobre algumas variables. Por exemplo, a function de loop

 sum(n) { int i = 1, k = 0; while( i <= n ) { k += i; ++i; } return k; } 

é equivalente à (s) function (ões) recursiva (s) da cauda

 sum_aux(n,i,k) { if( i <= n ) { return sum_aux(n,i+1,k+i); } else { return k; } } sum(n) { return sum_aux(n,1,0); } 

(Essa "quebra automática" da function recursiva da cauda com uma function com menos parâmetros é uma expressão funcional comum.)

Este trecho do livro Programação em Lua mostra como fazer uma recursion de cauda adequada (em Lua, mas deve se aplicar ao Lisp também) e por que é melhor.

Uma chamada de cauda [tail recursion] é uma espécie de goto vestido como uma chamada. Uma chamada de retorno acontece quando uma function chama outra como sua última ação, por isso não tem mais nada a fazer. Por exemplo, no código a seguir, a chamada para g é uma chamada final:

 function f (x) return g(x) end 

Depois de f chama g , não tem mais nada para fazer. Em tais situações, o programa não precisa retornar à function de chamada quando a function chamada terminar. Portanto, após a chamada final, o programa não precisa manter nenhuma informação sobre a function de chamada na pilha. …

Como uma chamada de cauda apropriada não usa espaço de pilha, não há limite no número de chamadas finais “aninhadas” que um programa pode fazer. Por exemplo, podemos chamar a seguinte function com qualquer número como argumento; nunca vai transbordar a pilha:

 function foo (n) if n > 0 then return foo(n - 1) end end 

Como eu disse anteriormente, uma chamada de cauda é uma espécie de goto. Como tal, uma aplicação bastante útil de chamadas finais apropriadas em Lua é para programar máquinas de estado. Tais aplicativos podem representar cada estado por uma function; mudar de estado é ir para (ou chamar) uma function específica. Como exemplo, vamos considerar um simples jogo de labirinto. O labirinto tem várias salas, cada uma com até quatro portas: norte, sul, leste e oeste. Em cada etapa, o usuário entra em uma direção de movimento. Se houver uma porta nessa direção, o usuário vai para a sala correspondente; caso contrário, o programa imprime um aviso. O objective é ir de uma sala inicial para uma sala final.

Este jogo é uma máquina de estado típica, onde a sala atual é o estado. Podemos implementar esse labirinto com uma function para cada sala. Usamos chamadas finais para passar de uma sala para outra. Um pequeno labirinto com quatro salas poderia ser assim:

 function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end 

Então você vê, quando você faz uma chamada recursiva como:

 function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end 

Esta não é a cauda recursiva porque você ainda tem coisas a fazer (adicionar 1) nessa function depois que a chamada recursiva é feita. Se você inserir um número muito alto, isso provavelmente causará um estouro de pilha.

Usando recursion regular, cada chamada recursiva envia outra input para a pilha de chamadas. Quando a recursion for concluída, o aplicativo terá que abrir cada input até o fim.

Com recursion de cauda, ​​o compilador é capaz de reduzir a pilha para uma input, para que você economize espaço de pilha … Uma consulta recursiva grande pode realmente causar um estouro de pilha.

Basicamente, as recursões de cauda podem ser otimizadas em iteração.

Em vez de explicá-lo com palavras, aqui está um exemplo. Esta é uma versão do esquema da function fatorial:

 (define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1))))) 

Aqui está uma versão do fatorial que é recursiva à cauda:

 (define factorial (letrec ((fact (lambda (x accum) (if (= x 0) accum (fact (- x 1) (* accum x)))))) (lambda (x) (fact x 1)))) 

Você notará na primeira versão que a chamada recursiva para o fato é alimentada na expressão de multiplicação e, portanto, o estado deve ser salvo na pilha ao fazer a chamada recursiva. Na versão recursiva da cauda não há outra expressão S esperando pelo valor da chamada recursiva, e como não há mais trabalho a ser feito, o estado não precisa ser salvo na pilha. Como regra, as funções recursivas de cauda Scheme usam espaço de pilha constante.

O arquivo do jargão tem isso a dizer sobre a definição da recursion da cauda:

recursion da cauda /n./

Se você não está cansado disso, veja a recursion da cauda.

A recursion de cauda refere-se à chamada recursiva sendo a última na última instrução lógica no algoritmo recursivo.

Normalmente, na recursion, você tem um caso base que é o que interrompe as chamadas recursivas e começa a aparecer na pilha de chamadas. Para usar um exemplo clássico, embora mais C-ish do que Lisp, a function fatorial ilustra a recursion da cauda. A chamada recursiva ocorre após a verificação da condição do caso base.

 factorial(x, fac) { if (x == 1) return fac; else return factorial(x-1, x*fac); } 

Note que a chamada inicial para fatorial deve ser fatorial (n, 1) onde n é o número para o qual o fatorial deve ser calculado.

Isso significa que, em vez de precisar pressionar o ponteiro de instrução na pilha, você pode simplesmente pular para o início de uma function recursiva e continuar a execução. Isso permite que as funções sejam recalculadas indefinidamente sem transbordar a pilha.

Eu escrevi uma postagem no blog sobre o assunto, que tem exemplos charts de como os frameworks da pilha se parecem.

Aqui está um trecho de código rápido comparando duas funções. A primeira é a recursion tradicional para encontrar o fatorial de um determinado número. O segundo usa a recursion da cauda.

Muito simples e intuitivo de entender.

Uma maneira fácil de saber se uma function recursiva é recursiva na cauda, ​​é se ela retornar um valor concreto no caso base. Significa que não retorna 1 ou verdadeiro ou algo assim. É mais provável que retorne alguma variante de um dos parâmetros do método.

Outra maneira é dizer se a chamada recursiva está livre de qualquer adição, aritmética, modificação, etc … O que significa nada mais que uma chamada recursiva pura.

 public static int factorial(int mynumber) { if (mynumber == 1) { return 1; } else { return mynumber * factorial(--mynumber); } } public static int tail_factorial(int mynumber, int sofar) { if (mynumber == 1) { return sofar; } else { return tail_factorial(--mynumber, sofar * mynumber); } } 

Em Java, aqui está uma possível implementação recursiva da function Fibonacci:

 public int tailRecursive(final int n) { if (n <= 2) return 1; return tailRecursiveAux(n, 1, 1); } private int tailRecursiveAux(int n, int iter, int acc) { if (iter == n) return acc; return tailRecursiveAux(n, ++iter, acc + iter); } 

Compare isso com a implementação recursiva padrão:

 public int recursive(final int n) { if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2); } 

A melhor maneira de eu entender a tail call recursion é: um caso especial de recursion em que a última chamada (ou a chamada final ) é a própria function.

Comparando os exemplos fornecidos no Python:

 def recsum(x): if x == 1: return x else: return x + recsum(x - 1) 

^ RECURSÃO

 def tailrecsum(x, running_total=0): if x == 0: return running_total else: return tailrecsum(x - 1, running_total + x) 

^ RECURSÃO DA CAUDA

Como você pode ver na versão recursiva geral, a chamada final no bloco de código é x + recsum(x - 1) . Então, depois de chamar o método recsum , há outra operação que é x + ..

No entanto, na versão recursiva tail, a chamada final (ou a chamada final) no bloco de código é tailrecsum(x - 1, running_total + x) que significa que a última chamada é feita para o método em si e nenhuma operação depois disso.

Este ponto é importante porque a recursion de cauda como visto aqui não está fazendo a memory crescer porque quando a VM subjacente vê uma function chamando-se em uma posição final (a última expressão a ser avaliada em uma function), ela elimina o quadro de pilha atual, que é conhecido como Tail Call Optimization (TCO).

EDITAR

NB Tenha em mente que o exemplo acima está escrito em Python, cujo tempo de execução não suporta TCO. Este é apenas um exemplo para explicar o ponto. O TCO é suportado em linguagens como Scheme, Haskell etc.

Aqui está um exemplo de Common Lisp que faz fatoriais usando recursion de cauda. Devido à natureza sem pilha, pode-se realizar cálculos fatoriais insanamente grandes …

 (defun ! (n &optional (product 1)) (if (zerop n) product (! (1- n) (* product n)))) 

E então, por diversão, você poderia tentar (format nil "~R" (! 25))

aqui está uma versão Perl 5 da function tailrecsum mencionada anteriormente.

 sub tail_rec_sum($;$){ my( $x,$running_total ) = (@_,0); return $running_total unless $x; @_ = ($x-1,$running_total+$x); goto &tail_rec_sum; # throw away current stack frame } 

Em suma, uma recursion de cauda tem a chamada recursiva como a última declaração na function para que ela não precise aguardar a chamada recursiva.

Portanto, esta é uma recursion de cauda, ​​ou seja, N (x – 1, p * x) é a última declaração na function onde o compilador é inteligente para descobrir que pode ser otimizado para um loop for (fatorial). O segundo parâmetro p carrega o valor do produto intermediário.

 function N(x, p) { return x == 1 ? p : N(x - 1, p * x); } 

Esta é a maneira não-recursiva de gravar a function fatorial acima (embora alguns compiladores de C ++ possam otimizá-la de qualquer maneira).

 function N(x) { return x == 1 ? 1 : x * N(x - 1); } 

mas isso não é:

 function F(x) { if (x == 1) return 0; if (x == 2) return 1; return F(x - 1) + F(x - 2); } 

Eu escrevi um longo post intitulado ” Entendendo a recursion de cauda – Visual Studio C ++ – Assembly View ”

insira a descrição da imagem aqui

Eu não sou um programador Lisp, mas acho que isso vai ajudar.

Basicamente é um estilo de programação tal que a chamada recursiva é a última coisa que você faz.

Para entender algumas das principais diferenças entre a recursion de chamada de cauda e a recursion de chamadas não-finais, podemos explorar as implementações .NET dessas técnicas.

Aqui está um artigo com alguns exemplos em C #, F # e C ++ \ CLI: Recursão de Cauda em Recursão em C #, F # e C ++ \ CLI .

C # não otimiza para recursion de chamada de cauda enquanto F # faz.

As diferenças de princípio envolvem loops vs. cálculo lambda. C # é projetado com loops em mente, enquanto F # é construído a partir dos princípios do cálculo Lambda. Para um livro muito bom (e gratuito) sobre os princípios do cálculo Lambda, veja: Estrutura e Interpretação de Programas de Computador, por Abelson, Sussman e Sussman .

Quanto às chamadas finais em F #, para um artigo introdutório muito bom, consulte: Introdução detalhada às chamadas finais em F # . Finalmente, aqui está um artigo que aborda a diferença entre a recursion não-final e a recursion da cauda (em F #): Recursão da cauda versus recursion não-cauda em F afiada .

Se você quiser ler sobre algumas das diferenças de design da recursion de call tail entre C # e F #, consulte: Gerando código de chamada de cauda em C # e F # .

Se você se importa o suficiente para saber quais condições impedem que o compilador C # execute otimizações de chamada de ponta, consulte este artigo: Condições de chamada de retorno do JIT CLR .

Este é um trecho de Estrutura e Interpretação de Programas de Computador sobre recursion de cauda.

Ao contrastar iteração e recursion, devemos ter cuidado para não confundir a noção de um processo recursivo com a noção de um procedimento recursivo. Quando descrevemos um procedimento como recursivo, estamos nos referindo ao fato sintático de que a definição do procedimento se refere (direta ou indiretamente) ao próprio procedimento. Mas quando descrevemos um processo como seguindo um padrão que é, digamos, linearmente recursivo, estamos falando sobre como o processo evolui, não sobre a syntax de como um procedimento é escrito. Pode parecer preocupante referirmo-nos a um procedimento recursivo, como factorial, como gerador de um processo iterativo. No entanto, o processo é realmente iterativo: seu estado é capturado completamente por suas três variables ​​de estado, e um intérprete precisa controlar apenas três variables ​​para executar o processo.

Uma razão pela qual a distinção entre processo e procedimento pode ser confusa é que a maioria das implementações de linguagens comuns (incluindo Ada, Pascal e C) são projetadas de tal maneira que a interpretação de qualquer procedimento recursivo consome uma quantidade de memory que cresce com o processo. número de chamadas de procedimento, mesmo quando o processo descrito é, em princípio, iterativo. Como conseqüência, essas linguagens podem descrever processos iterativos apenas recorrendo a “construções de looping” de finalidade especial, como do, repeat, until, for e while. A implementação do Scheme não compartilha esse defeito. Ele executará um processo iterativo em espaço constante, mesmo que o processo iterativo seja descrito por um procedimento recursivo. Uma implementação com essa propriedade é chamada tail-recursive. Com uma implementação recursiva de cauda, ​​a iteração pode ser expressa usando o mecanismo de chamada de procedimento comum, para que as construções de iteração especiais sejam úteis apenas como açúcar sintático.

A recursion da cauda é a vida que você está vivendo agora. Você recicla constantemente o mesmo quadro de pilha, repetidamente, porque não há razão ou meio para retornar a um quadro “anterior”. O passado acabou e terminado com isso pode ser descartado. Você obtém um quadro, sempre mudando para o futuro, até que seu processo inevitavelmente morra.

A analogia se quebra quando você considera que alguns processos podem utilizar frames adicionais, mas ainda são considerados tail-recursive se a pilha não crescer infinitamente.

Recursão significa uma function chamando a si mesma. Por exemplo:

 (define (un-ended name) (un-ended 'me) (print "How can I get here?")) 

Tail-Recursion significa a recursion que conclui a function:

 (define (un-ended name) (print "hello") (un-ended 'me)) 

Veja, a última coisa que a function un-ended (procedimento, no jargão Scheme) faz é chamar a si mesma. Outro exemplo (mais útil) é:

 (define (map lst op) (define (helper done left) (if (nil? left) done (helper (cons (op (car left)) done) (cdr left)))) (reverse (helper '() lst))) 

No procedimento auxiliar, a ÚLTIMA coisa que ele faz se não for nulo é chamar a si mesmo (APÓS algo e algo cdr). Isso é basicamente como você mapeia uma lista.

A recursion final tem uma grande vantagem de que o interperter (ou compilador, dependente da linguagem e do fornecedor) pode otimizá-lo e transformá-lo em algo equivalente a um loop while. De fato, na tradição do Scheme, a maior parte do loop “for” e “while” é feito de maneira recursiva (não há por enquanto, até onde eu sei).

Esta pergunta tem muitas ótimas respostas … mas não posso deixar de falar com uma alternativa sobre como definir “recursion de cauda”, ou pelo menos “recursion de cauda apropriada”. Ou seja: deve-se olhar para ela como uma propriedade de uma determinada expressão em um programa? Ou alguém deveria olhar para isto como uma propriedade de uma implementação de uma linguagem de programação ?

Para mais sobre este último ponto de vista, há um artigo clássico de Will Clinger, “Recursão da Cauda Adequada e Eficiência Espacial” (PLDI 1998), que definiu “recursion de cauda apropriada” como uma propriedade de implementação de linguagem de programação. A definição é construída para permitir ignorar os detalhes da implementação (como, por exemplo, se a pilha de chamadas é representada por meio da pilha de tempo de execução ou por meio de uma lista de frameworks vinculada alocada por heap).

Para isso, utiliza uma análise assintótica: não o tempo de execução do programa como normalmente se vê, mas sim o uso do espaço do programa. Dessa forma, o uso de espaço de uma linked list alocada por heap versus uma pilha de chamada de tempo de execução acaba sendo assintoticamente equivalente; Assim, é possível ignorar esse detalhe de implementação da linguagem de programação (um detalhe que certamente importa bastante na prática, mas pode atrapalhar bastante as águas quando se tenta determinar se uma dada implementação está satisfazendo a exigência de ser “propriedade tail recursiva” )

Vale a pena estudar cuidadosamente o estudo por vários motivos:

  • Ele fornece uma definição indutiva das expressões finais e das chamadas finais de um programa. (Tal definição, e por que tais chamadas são importantes, parece ser o assunto da maioria das outras respostas dadas aqui.)

    Aqui estão essas definições, apenas para fornecer um sabor do texto:

    Definição 1 As expressões finais de um programa escrito em Core Scheme são definidas indutivamente da seguinte maneira.

    1. O corpo de uma expressão lambda é uma expressão de cauda
    2. Se (if E0 E1 E2) for uma expressão final, então E1 e E2 são expressões finais.
    3. Nada mais é uma expressão de rabo.

    Definição 2 Uma chamada final é uma expressão final que é uma chamada de procedimento.

(uma chamada recursiva final, ou como o jornal diz, “chamada auto-tail” é um caso especial de uma chamada de cauda onde o procedimento é invocado em si.)

  • Ele fornece definições formais para seis “máquinas” diferentes para avaliar o Esquema Principal, em que cada máquina tem o mesmo comportamento observável, exceto para a class de complexidade de espaço assintótico em que cada uma está.

    Por exemplo, depois de dar definições para máquinas com respectivamente, 1. gerenciamento de memory baseado em pilha, 2. garbage collection, mas sem chamadas finais, 3. garbage collection e chamadas finais, o papel continua adiante com estratégias de gerenciamento de armazenamento ainda mais avançadas, como 4. “recursion da cauda do evlis”, onde o ambiente não precisa ser preservado na avaliação do argumento da última sub-expressão em uma chamada de cauda, ​​5. reduzindo o ambiente de um fechamento para apenas as variables ​​livres daquele fechamento, e 6. a chamada semântica “safe-for-space”, como definida por Appel e Shao .

  • A fim de provar que as máquinas realmente pertencem a seis classs distintas de complexidade espacial, o papel, para cada par de máquinas em comparação, fornece exemplos concretos de programas que exporão o blowup de espaço assintótico em uma máquina, mas não na outra.


(Lendo minha resposta agora, não tenho certeza se sou realmente capaz de capturar os pontos cruciais do artigo de Clinger . Mas, infelizmente, não posso dedicar mais tempo para desenvolver essa resposta agora.)

Uma recursion final é uma function recursiva em que a function chama a si mesma no final (“tail”) da function na qual nenhum cálculo é feito após o retorno da chamada recursiva. Muitos compiladores otimizam para alterar uma chamada recursiva para uma cauda recursiva ou uma chamada iterativa.

Considere o problema de calcular o fatorial de um número.

Uma abordagem direta seria:

  factorial(n): if n==0 then 1 else n*factorial(n-1) 

Suponha que você chame fatorial (4). A tree de recursion seria:

  factorial(4) / \ 4 factorial(3) / \ 3 factorial(2) / \ 2 factorial(1) / \ 1 factorial(0) \ 1 

A profundidade máxima de recursion no caso acima é O (n).

No entanto, considere o seguinte exemplo:

 factAux(m,n): if n==0 then m; else factAux(m*n,n-1); factTail(n): return factAux(1,n); 

Árvore de recursion para factTail (4) seria:

 factTail(4) | factAux(1,4) | factAux(4,3) | factAux(12,2) | factAux(24,1) | factAux(24,0) | 24 

Aqui também, a profundidade máxima de recursion é O (n), mas nenhuma das chamadas adiciona qualquer variável extra à pilha. Portanto, o compilador pode acabar com uma pilha.

Existem dois tipos básicos de recursões: recursion da cabeça e recursion da cauda.

Na cabeça recursion , uma function faz sua chamada recursiva e, em seguida, executa mais alguns cálculos, talvez usando o resultado da chamada recursiva, por exemplo.

Em uma function recursiva de cauda , todos os cálculos acontecem primeiro e a chamada recursiva é a última coisa que acontece.

Extraído deste post incrível. Por favor, considere a leitura.