Por que os loops são mais rápidos que a recursão?

Na prática, entendo que qualquer recursão pode ser escrita como um loop (e vice-versa (?)) E, se medirmos com computadores reais, verificamos que os loops são mais rápidos que a recursão para o mesmo problema. Mas existe alguma teoria que faça essa diferença ou seja principalmente emprical?

A razão pela qual os loops são mais rápidos que a recursão é fácil.
Um loop se parece com isso na montagem.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Um único salto condicional e alguma contabilidade para o contador de loops.

A recursão (quando não é ou não pode ser otimizada pelo compilador) tem a seguinte aparência:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

É muito mais complexo e você recebe pelo menos 3 saltos (1 teste para ver se foram feitos, uma chamada e um retorno).
Também em recursão, os parâmetros precisam ser configurados e buscados.
Nada disso é necessário em um loop, porque todos os parâmetros já estão configurados.

Teoricamente, os parâmetros também podem permanecer no local com recursão, mas nenhum compilador que eu conheça realmente chega tão longe em sua otimização.

Diferenças entre uma chamada e um jmp
Um par de retorno de chamada não é muito mais caro que o jmp. O par leva 2 ciclos e o jmp leva 1; dificilmente perceptível.
Nas convenções de chamada que suportam parâmetros de registro, a sobrecarga para parâmetros é mínima, mas mesmo os parâmetros da pilha são baratos , desde que os buffers da CPU não excedam .
É a sobrecarga da configuração de chamada ditada pela convenção de chamada e pelo manuseio de parâmetros em uso que diminui a recursão.
Isso depende muito da implementação.

Exemplo de manipulação incorreta da recursão Por exemplo, se um parâmetro é passado e contado como referência (por exemplo, um parâmetro do tipo não gerenciado por const), ele adiciona 100 ciclos fazendo um ajuste bloqueado da contagem de referência, prejudicando totalmente o desempenho em relação a um loop.
Em idiomas ajustados para recursão, esse mau comportamento não ocorre.

Otimização da CPU
A outra razão pela qual a recursão é mais lenta é que ela funciona contra os mecanismos de otimização nas CPUs.
Os retornos só podem ser previstos corretamente se não houver muitos deles em uma linha. A CPU possui um buffer de pilha de retorno com algumas poucas entradas. Uma vez esgotados, todo retorno adicional será imprevisível, causando enormes atrasos.
Em qualquer CPU que usa uma pilha com retorno de pilha, a recursão baseada em chamada que excede o tamanho do buffer é melhor evitar.

Sobre exemplos triviais de código usando recursão
Se você usar um exemplo trivial de recursão, como a geração de números de Fibonacci, esses efeitos não ocorrerão, porque qualquer compilador que 'conhece' sobre recursão o transformará em um loop, assim como qualquer programador que se preze seria.
Se você executar esses exemplos triviais em um ambiente que não seja otimizado corretamente, a pilha de chamadas crescerá (desnecessariamente) fora dos limites.

Sobre a recursão da cauda
Observe que algumas vezes o compilador otimiza a recursão da cauda alterando-a em um loop. É melhor confiar apenas nesse comportamento em idiomas que tenham um bom histórico conhecido a esse respeito.
Muitos idiomas inserem código de limpeza oculto antes do retorno final, impedindo a otimização da recursão da cauda.

Confusão entre verdadeira e pseudo-recursão
Se o seu ambiente de programação transformar seu código-fonte recursivo em um loop, é provável que não seja uma recursão verdadeira que está sendo executada.
A verdadeira recursão requer um armazenamento de migalhas de pão, para que a rotina recursiva possa rastrear suas etapas após a saída.
É o manuseio dessa trilha que torna a recursão mais lenta do que usar um loop. Esse efeito é ampliado pelas implementações atuais da CPU, conforme descrito acima.

Efeito do ambiente de programação
Se a sua linguagem estiver sintonizada com a otimização da recursão, vá em frente e use a recursão em todas as oportunidades. Na maioria dos casos, o idioma transformará sua recursão em algum tipo de loop.
Nos casos em que não é possível, o programador também seria pressionado. Se sua linguagem de programação não estiver ajustada para recursão, deve ser evitada, a menos que o domínio seja adequado para recursão.
Infelizmente, muitos idiomas não lidam bem com a recursão.

Uso indevido de recursão
Não há necessidade de calcular a sequência de Fibonacci usando recursão, na verdade, é um exemplo patológico.
A recursão é melhor usada em idiomas que a suportam explicitamente ou em domínios em que a recursão brilha, como o tratamento de dados armazenados em uma árvore.

Entendo que qualquer recursão pode ser escrita como um loop

Sim, se você estiver disposto a colocar a carroça diante do cavalo.
Todas as instâncias de recursão podem ser gravadas como um loop. Algumas dessas instâncias exigem o uso de uma pilha explícita, como armazenamento.
Se você precisar rolar sua própria pilha apenas para transformar um código recursivo em um loop, use a recursão simples.
A menos que você tenha necessidades especiais, como o uso de enumeradores em uma estrutura em árvore, e não tenha suporte a idiomas adequado.

Essas outras respostas são enganosas. Concordo que eles declaram detalhes da implementação que podem explicar essa disparidade, mas exageram o caso. Conforme sugerido corretamente pelo jmite, eles são orientados à implementação para implementações interrompidas de chamadas de função / recursão. Muitas linguagens implementam loops via recursão, portanto os loops claramente não serão mais rápidos nesses idiomas. A recursão não é menos eficiente que o loop (quando ambos são aplicáveis) na teoria. Deixe-me citar o resumo do artigo de Guy Steele, de 1977, Desmistificando o Mito "Expensive Procedure Call" ou, Implementações de Procedimentos Consideradas Prejudiciais ou Lambda: o GOTO Final

O folclore afirma que as declarações GOTO são "baratas", enquanto as chamadas de procedimento são "caras". Esse mito é amplamente resultado de implementações de linguagem mal projetadas. O crescimento histórico desse mito é considerado. São discutidas idéias teóricas e uma implementação existente que desmascaram esse mito. É mostrado que o uso irrestrito de chamadas de procedimento permite uma grande liberdade estilística. Em particular, qualquer fluxograma pode ser escrito como um programa "estruturado" sem a introdução de variáveis ​​extras. A dificuldade com a instrução GOTO e a chamada de procedimento é caracterizada como um conflito entre conceitos abstratos de programação e construções de linguagem concretas.

O "conflito entre conceitos abstratos de programação e construções concretas de linguagem" pode ser visto pelo fato de que a maioria dos modelos teóricos, por exemplo, o cálculo lambda não tipado , não possui uma pilha . Obviamente, esse conflito não é necessário, como o artigo acima ilustra e também é demonstrado por idiomas que não têm mecanismo de iteração além de recursão como Haskell.

fixfix f x = f (fix f) x$(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$

Agora, por um exemplo. Definir factcomo

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Aqui está a avaliação de fact 3onde, para compacidade, vou usar gcomo sinônimo para fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), ie fact = g 1. Isso não afeta meu argumento.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Você pode ver a partir da forma sem olhar para os detalhes que não há crescimento e cada iteração precisa da mesma quantidade de espaço. (Tecnicamente, o resultado numérico cresce, o que é inevitável e igualmente verdadeiro para um whileloop.) Desafio você a apontar a "pilha" sem limites aqui.

Parece que a semântica arquetípica do cálculo lambda já faz o que é comumente chamado de "otimização de chamada de cauda". Obviamente, nenhuma "otimização" está acontecendo aqui. Não há regras especiais aqui para chamadas "finais" em oposição às chamadas "normais". Por esse motivo, é difícil fornecer uma caracterização "abstrata" do que a "otimização" da chamada de cauda está fazendo, pois em muitas caracterizações abstratas da semântica da chamada de função, não há nada que a "otimização" de chamada de cauda faça!

Que a definição análoga de factem muitos idiomas "estouros de pilha" é uma falha desses idiomas em implementar corretamente a semântica das chamadas de função. (Alguns idiomas têm uma desculpa.) A situação é aproximadamente análoga a uma implementação de idioma que implementou matrizes com listas vinculadas. A indexação em tais "matrizes" seria então uma operação O (n) que não atende à expectativa de matrizes. Se eu fizesse uma implementação separada da linguagem, que usava matrizes reais em vez de listas vinculadas, você não diria que implementei "otimização de acesso à matriz", diria que eu corrigi uma implementação quebrada de matrizes.

Então, respondendo à resposta de Veedrac. Pilhas não são "fundamentais" para recursão . Na medida em que o comportamento "empilhável" ocorre durante o curso da avaliação, isso só pode acontecer nos casos em que loops (sem uma estrutura de dados auxiliar) não seriam aplicáveis ​​em primeiro lugar! Em outras palavras, posso implementar loops com recursão com exatamente as mesmas características de desempenho. De fato, Scheme e SML contêm construções de loop, mas ambas as definem em termos de recursão (e, pelo menos em Scheme, dosão frequentemente implementadas como uma macro que se expande em chamadas recursivas.) Da mesma forma, para a resposta de Johan, nada diz O compilador deve emitir o assembly que Johan descreveu para recursão. De fato,exatamente a mesma montagem, independentemente de você usar loops ou recursão. A única vez que o compilador seria (um pouco) obrigado a emitir assembly como o que Johan descreve é ​​quando você está fazendo algo que não é expressável por um loop de qualquer maneira. Conforme descrito no artigo de Steele e demonstrado pela prática real de linguagens como Haskell, Scheme e SML, não é "extremamente raro" que chamadas de cauda possam ser "otimizadas", elas sempre podemser "otimizado". Se um determinado uso da recursão será executado no espaço constante depende de como está escrito, mas as restrições que você precisa aplicar para tornar isso possível são as restrições necessárias para ajustar seu problema na forma de um loop. (Na verdade, eles são menos rigorosos. Existem problemas, como máquinas de estado de codificação, que são tratados de maneira mais limpa e eficiente por meio de chamadas tails, em oposição a loops que exigiriam variáveis ​​auxiliares.) Novamente, a única recursão de tempo que exige mais trabalho é quando seu código não é um loop de qualquer maneira.

Meu palpite é que Johan está se referindo aos compiladores C que têm restrições arbitrárias sobre quando ele executará a "otimização" da chamada de cauda. Provavelmente, Johan também está se referindo a idiomas como C ++ e Rust quando fala sobre "idiomas com tipos gerenciados". O idioma RAII do C ++ e presente no Rust também faz coisas que superficialmente parecem chamadas de cauda, ​​não chamadas de cauda (porque os "destruidores" ainda precisam ser chamados). Houve propostas para usar uma sintaxe diferente para ativar uma semântica ligeiramente diferente que permitiria recursão de cauda (ou seja, chamar destruidores antesa chamada final e obviamente não permitir o acesso a objetos "destruídos"). (A coleta de lixo não tem esse problema, e todo o Haskell, SML e Scheme são linguagens de coleta de lixo.) De uma maneira bem diferente, alguns idiomas, como o Smalltalk, expõem a "pilha" como um objeto de primeira classe. casos, a "pilha" não é mais um detalhe de implementação, embora isso não impeça a separação de tipos de chamadas com diferentes semânticas. (Java diz que não pode devido à maneira como lida com alguns aspectos da segurança, mas isso é realmente falso .)

Na prática, a prevalência de implementações interrompidas de chamadas de função vem de três fatores principais. Primeiro, muitos idiomas herdam a implementação interrompida de sua linguagem de implementação (geralmente C). Segundo, o gerenciamento determinístico de recursos é bom e torna o problema mais complicado, embora apenas algumas línguas o ofereçam. Terceiro, e, na minha experiência, o motivo pelo qual a maioria das pessoas se importa é que elas querem rastreamentos de pilha quando ocorrem erros para fins de depuração. Somente a segunda razão é aquela que pode ser potencialmente motivada teoricamente.

Fundamentalmente, a diferença é que a recursão inclui uma pilha, uma estrutura de dados auxiliar que você provavelmente não deseja, enquanto os loops não o fazem automaticamente. Somente em casos raros, um compilador típico é capaz de deduzir que você realmente não precisa da pilha, afinal.

Se você comparar loops operando manualmente em uma pilha alocada (por exemplo, através de um ponteiro para acumular memória), normalmente você os achará não mais rápidos ou mais lentos do que usando a pilha de hardware.