Recursão ou Iteração?
https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Haverá um impacto no desempenho se usarmos um loop em vez de recursão ou vice-versa em algoritmos onde ambos podem servir ao mesmo propósito?Por exemplo:Verifique se a string fornecida é um palíndromo.Tenho visto muitos programadores usando a recursão como um meio de mostrar quando um algoritmo de iteração simples pode ser adequado.O compilador desempenha um papel vital na decisão do que usar?
Solução
É possível que a recursão seja mais cara, dependendo se a função recursiva é cauda recursiva (a última linha é uma chamada recursiva).Recursão de cauda deve ser reconhecido pelo compilador e otimizado para sua contraparte iterativa (mantendo a implementação concisa e clara que você tem em seu código).
Eu escreveria o algoritmo da maneira que fizesse mais sentido e fosse mais claro para o pobre otário (seja você mesmo ou outra pessoa) que precisa manter o código em alguns meses ou anos.Se você tiver problemas de desempenho, crie um perfil de seu código e só então procure otimizar passando para uma implementação iterativa.Você pode querer investigar memorização e programaçao dinamica.
Outras dicas
Os loops podem proporcionar um ganho de desempenho para o seu programa.A recursão pode proporcionar um ganho de desempenho para o seu programador.Escolha o que é mais importante na sua situação!
Comparar recursão com iteração é como comparar uma chave de fenda Phillips com uma chave de fenda chata.Na maior parte você poderia remova qualquer parafuso Phillips com cabeça chata, mas seria mais fácil se você usasse a chave de fenda projetada para esse parafuso, certo?
Alguns algoritmos apenas se prestam à recursão devido à forma como são projetados (sequências de Fibonacci, atravessando uma estrutura semelhante a uma árvore, etc.).A recursão torna o algoritmo mais sucinto e fácil de entender (portanto, compartilhável e reutilizável).
Além disso, alguns algoritmos recursivos usam "Avaliação Preguiçosa", o que os torna mais eficientes do que seus irmãos iterativos.Isso significa que eles só fazem cálculos caros no momento em que são necessários, e não sempre que o loop é executado.
Isso deve ser suficiente para você começar.Vou desenterrar alguns artigos e exemplos para você também.
Ligação 1: Haskel vs PHP (recursão vs iteração)
Aqui está um exemplo em que o programador teve que processar um grande conjunto de dados usando PHP.Ele mostra como teria sido fácil lidar com Haskel usando recursão, mas como o PHP não tinha uma maneira fácil de realizar o mesmo método, ele foi forçado a usar iteração para obter o resultado.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Ligação 2: Dominando a recursão
A maior parte da má reputação da recursão vem dos altos custos e da ineficiência das linguagens imperativas.O autor deste artigo fala sobre como otimizar algoritmos recursivos para torná-los mais rápidos e eficientes.Ele também explica como converter um loop tradicional em uma função recursiva e os benefícios de usar a recursão final.Suas palavras finais realmente resumiram alguns dos meus pontos-chave, eu acho:
"A programação recursiva oferece ao programador uma maneira melhor de organizar o código de uma maneira que seja mantida e logicamente consistente".
Ligação 3: A recursão é sempre mais rápida que o loop?(Responder)
Aqui está um link para uma resposta a uma pergunta sobre stackoverflow semelhante à sua.O autor aponta que muitos dos benchmarks associados à recorrência ou ao loop são muito específico do idioma.Linguagens imperativas são normalmente mais rápidas usando um loop e mais lentas com recursão e vice-versa para linguagens funcionais.Acho que o ponto principal a ser extraído deste link é que é muito difícil responder à pergunta em um sentido cego agnóstico de linguagem/situação.
A recursão é mais cara em memória, pois cada chamada recursiva geralmente requer que um endereço de memória seja colocado na pilha - para que mais tarde o programa possa retornar a esse ponto.
Ainda assim, há muitos casos em que a recursão é muito mais natural e legível que os loops - como quando se trabalha com árvores.Nesses casos, eu recomendaria manter a recursão.
Normalmente, seria de esperar que a penalidade de desempenho estivesse na outra direção.Chamadas recursivas podem levar à construção de frames de pilha extras;a penalidade para isso varia.Além disso, em algumas linguagens como Python (mais corretamente, em algumas implementações de algumas linguagens...), você pode facilmente atingir limites de pilha para tarefas que você pode especificar recursivamente, como encontrar o valor máximo em uma estrutura de dados em árvore.Nesses casos, você realmente quer ficar com os loops.
Escrever boas funções recursivas pode reduzir um pouco a penalidade de desempenho, assumindo que você tenha um compilador que otimize recursões finais, etc.(Também verifique novamente para ter certeza de que a função é realmente recursiva - é uma daquelas coisas em que muitas pessoas cometem erros.)
Além dos casos "extremos" (computação de alto desempenho, profundidade de recursão muito grande, etc.), é preferível adotar a abordagem que expressa mais claramente sua intenção, é bem projetada e pode ser mantida.Otimize somente após identificar uma necessidade.
A recursão é melhor que a iteração para problemas que podem ser divididos em múltiplo, pedaços menores.
Por exemplo, para criar um algoritmo Fibonnaci recursivo, você divide fib(n) em fib(n-1) e fib(n-2) e calcula ambas as partes.A iteração permite apenas repetir uma única função indefinidamente.
No entanto, Fibonacci é na verdade um exemplo quebrado e acho que a iteração é realmente mais eficiente.Observe que fib(n) = fib(n-1) + fib(n-2) e fib(n-1) = fib(n-2) + fib(n-3).fib(n-1) é calculado duas vezes!
Um exemplo melhor é um algoritmo recursivo para uma árvore.O problema de análise do nó pai pode ser dividido em múltiplo problemas menores de análise de cada nó filho.Ao contrário do exemplo de Fibonacci, os problemas menores são independentes uns dos outros.
Então, sim - a recursão é melhor que a iteração para problemas que podem ser divididos em problemas múltiplos, menores, independentes e semelhantes.
Seu desempenho piora ao usar recursão porque chamar um método, em qualquer linguagem, implica muito preparo:o código de chamada publica um endereço de retorno, parâmetros de chamada, algumas outras informações de contexto, como registros do processador, podem ser salvas em algum lugar e, no momento do retorno, o método chamado publica um valor de retorno que é então recuperado pelo chamador e qualquer informação de contexto que foi anteriormente salvo será restaurado.a diferença de desempenho entre uma abordagem iterativa e uma abordagem recursiva está no tempo que essas operações levam.
Do ponto de vista da implementação, você realmente começa a notar a diferença quando o tempo necessário para lidar com o contexto de chamada é comparável ao tempo necessário para a execução do seu método.Se o seu método recursivo demorar mais para ser executado, então a parte de gerenciamento de contexto de chamada, siga o caminho recursivo, pois o código geralmente é mais legível e fácil de entender e você não notará a perda de desempenho.Caso contrário, torne-se iterativo por razões de eficiência.
Acredito que a recursão final em java não está otimizada no momento.Os detalhes estão espalhados por toda parte esse discussão sobre LtU e os links associados.Isto poderia será um recurso na próxima versão 7, mas aparentemente apresenta certas dificuldades quando combinado com Stack Inspection, pois alguns frames estariam faltando.Stack Inspection tem sido usado para implementar seu modelo de segurança refinado desde Java 2.
Há muitos casos em que ele fornece uma solução muito mais elegante do que o método iterativo, sendo o exemplo comum a travessia de uma árvore binária, portanto não é necessariamente mais difícil de manter.Em geral, as versões iterativas são um pouco mais rápidas (e durante a otimização podem substituir uma versão recursiva), mas as versões recursivas são mais simples de compreender e implementar corretamente.
A recursão é muito útil em algumas situações.Por exemplo, considere o código para encontrar o fatorial
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
Agora considere isso usando a função recursiva
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Observando esses dois, podemos ver que a recursão é fácil de entender.Mas se não for usado com cuidado, também pode estar sujeito a erros.Suponha que se perdermos if (input == 0), então o código será executado por algum tempo e geralmente termina com um estouro de pilha.
Em muitos casos, a recursão é mais rápida devido ao cache, o que melhora o desempenho.Por exemplo, aqui está uma versão iterativa da classificação por mesclagem usando a rotina de mesclagem tradicional.Ele será executado mais lentamente do que a implementação recursiva devido ao desempenho aprimorado do cache.
Implementação iterativa
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
Implementação recursiva
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS - foi o que contou o professor Kevin Wayne (Universidade de Princeton) no curso sobre algoritmos apresentado no Coursera.
Usando a recursão, você incorre no custo de uma chamada de função a cada "iteração", enquanto que com um loop, a única coisa que você normalmente paga é um incremento/decremento.Portanto, se o código do loop não for muito mais complicado que o código da solução recursiva, o loop geralmente será superior à recursão.
A recursão e a iteração dependem da lógica de negócios que você deseja implementar, embora na maioria dos casos possam ser usadas de forma intercambiável.A maioria dos desenvolvedores opta pela recursão porque é mais fácil de entender.
Depende do idioma.Em Java você deve usar loops.Linguagens funcionais otimizam a recursão.
Se você está apenas iterando em uma lista, então, claro, itere.
Algumas outras respostas mencionaram a travessia de árvore (em profundidade).É realmente um ótimo exemplo, porque é algo muito comum de se fazer em uma estrutura de dados muito comum.A recursão é extremamente intuitiva para este problema.
Confira os métodos de "localização" aqui:http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
A recursão é mais simples (e, portanto, mais fundamental) do que qualquer definição possível de uma iteração.Você pode definir um sistema Turing-completo com apenas um par de combinadores (sim, até mesmo a própria recursão é uma noção derivada em tal sistema). lambda o cálculo é um sistema fundamental igualmente poderoso, apresentando funções recursivas.Mas se você quiser definir uma iteração corretamente, precisará de muito mais primitivos para começar.
Quanto ao código - não, o código recursivo é de fato muito mais fácil de entender e manter do que um código puramente iterativo, já que a maioria das estruturas de dados são recursivas.É claro que, para acertar, seria necessária uma linguagem com suporte para funções e fechamentos de alta ordem, pelo menos - para obter todos os combinadores e iteradores padrão de maneira organizada.Em C++, é claro, soluções recursivas complicadas podem parecer um pouco feias, a menos que você seja um usuário assíduo de FC++ e similares.
Eu pensaria que na recursão (sem cauda) haveria um impacto no desempenho ao alocar uma nova pilha, etc., toda vez que a função fosse chamada (dependendo do idioma, é claro).
depende da "profundidade de recursão".depende de quanto a sobrecarga da chamada de função influenciará o tempo total de execução.
Por exemplo, calcular o fatorial clássico de forma recursiva é muito ineficiente devido a:- Risco de transbordamento de dados - Risco de transbordar de pilha - A chamada de chamadas de função ocupa 80% do tempo de execução
ao desenvolver um algoritmo min-max para análise de posição no jogo de xadrez que irá analisar N movimentos subsequentes pode ser implementado em recursão sobre a "profundidade de análise" (como estou fazendo ^_^)
Recursão?Por onde eu começo, o wiki dirá “é o processo de repetir itens de maneira semelhante”
Antigamente, quando eu estava fazendo C, a recursão em C++ era uma dádiva de Deus, coisas como "recursão de cauda".Você também encontrará muitos algoritmos de classificação que usam recursão.Exemplo de classificação rápida: http://alienryderflex.com/quicksort/
A recursão é como qualquer outro algoritmo útil para um problema específico.Talvez você não encontre um uso imediato ou frequente, mas haverá um problema e você ficará feliz por ele estar disponível.
Em C++, se a função recursiva for modelada, o compilador terá mais chances de otimizá-la, pois todas as deduções de tipo e instanciações de função ocorrerão em tempo de compilação.Os compiladores modernos também podem incorporar a função, se possível.Então, se alguém usar sinalizadores de otimização como -O3 ou -O2 em g++, então as recursões podem ter a chance de ser mais rápidas que as iterações.Em códigos iterativos, o compilador tem menos chance de otimizá-lo, pois já está no estado mais ou menos ideal (se escrito bem o suficiente).
No meu caso, eu estava tentando implementar a exponenciação de matrizes por quadratura usando objetos de matriz Armadillo, tanto de forma recursiva quanto iterativa.O algoritmo pode ser encontrado aqui... https://en.wikipedia.org/wiki/Exponenciation_by_squaring.Minhas funções foram modeladas e eu calculei 1,000,000 12x12 matrizes elevadas à potência 10.Obtive o seguinte resultado:
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
Esses resultados foram obtidos usando gcc-4.8 com sinalizador c++ 11 (-std=c++11) e Armadillo 6.1 com Intel mkl.O compilador Intel também mostra resultados semelhantes.
Mike está correto.A recursão da cauda é não otimizado pelo compilador Java ou pela JVM.Você sempre obterá um estouro de pilha com algo assim:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Você deve ter em mente que, ao usar recursão muito profunda, você encontrará Stack Overflow, dependendo do tamanho de pilha permitido.Para evitar isso, certifique-se de fornecer algum caso base que encerre sua recursão.
A recursão tem a desvantagem de que o algoritmo que você escreve usando a recursão tem complexidade de espaço O(n).Embora a abordagem iterativa tenha uma complexidade de espaço de O(1). Esta é a vantagem de usar iteração em vez de recursão.Então por que usamos recursão?
Veja abaixo.
Às vezes é mais fácil escrever um algoritmo usando recursão, enquanto é um pouco mais difícil escrever o mesmo algoritmo usando iteração. Nesse caso, se você optar por seguir a abordagem de iteração, você mesmo terá que lidar com a pilha.
Até onde eu sei, Perl não otimiza chamadas recursivas finais, mas você pode fingir.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
Quando chamado pela primeira vez, ele alocará espaço na pilha.Então ele mudará seus argumentos e reiniciará a sub-rotina, sem adicionar mais nada à pilha.Irá, portanto, fingir que nunca chamou a si mesmo, transformando-o num processo iterativo.
Observe que não há "my @_;" ou "local @_;", se você fizesse isso não funcionaria mais.
Usando apenas o Chrome 45.0.2454.85 m, a recursão parece ser muito mais rápida.
Aqui está o código:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
RESULTADOS
// 100 execuções usando loop for padrão
100x para execução em loop.Hora de concluir: 7,683ms
// 100 execuções usando abordagem recursiva funcional com recursão final
Execução de recursão 100x.Hora de concluir: 4,841ms
Na captura de tela abaixo, a recursão vence novamente por uma margem maior quando executada a 300 ciclos por teste
Se as iterações forem atômicas e muito mais caras do que enviar um novo stack frame e criando um novo tópico e você tem vários núcleos e seu ambiente de tempo de execução pode usar todos eles, então uma abordagem recursiva pode gerar um enorme aumento de desempenho quando combinada com multithreading.Se o número médio de iterações não for previsível, pode ser uma boa ideia usar um pool de threads que controlará a alocação de threads e evitará que seu processo crie muitos threads e sobrecarregue o sistema.
Por exemplo, em algumas linguagens, existem implementações recursivas de classificação por mesclagem multithread.
Mas, novamente, o multithreading pode ser usado com loop em vez de recursão; portanto, o bom funcionamento dessa combinação depende de mais fatores, incluindo o sistema operacional e seu mecanismo de alocação de threads.
Vou responder sua pergunta projetando uma estrutura de dados Haskell por "indução", que é uma espécie de "dual" para recursão.E então mostrarei como essa dualidade leva a coisas boas.
Apresentamos um tipo para uma árvore simples:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
Podemos ler esta definição como dizendo "Uma árvore é um galho (que contém duas árvores) ou é uma folha (que contém um valor de dados)".Então a folha é uma espécie de caso mínimo.Se uma árvore não é uma folha, então deve ser uma árvore composta contendo duas árvores.Estes são os únicos casos.
Vamos fazer uma árvore:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Agora, suponhamos que queremos adicionar 1 a cada valor da árvore.Podemos fazer isso ligando para:
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
Primeiro, observe que esta é na verdade uma definição recursiva.Toma os construtores de dados Branch e Leaf como casos (e como Leaf é mínimo e esses são os únicos casos possíveis), temos certeza de que a função será encerrada.
O que seria necessário para escrever addOne em um estilo iterativo?Como será o loop em um número arbitrário de ramificações?
Além disso, esse tipo de recursão muitas vezes pode ser fatorado em termos de um "functor".Podemos transformar árvores em functores definindo:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
e definindo:
addOne' = fmap (+1)
Podemos fatorar outros esquemas de recursão, como o catamorfismo (ou dobramento) para um tipo de dados algébrico.Usando um catamorfismo, podemos escrever:
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
O estouro de pilha só ocorrerá se você estiver programando em uma linguagem que não tenha gerenciamento de memória integrado....Caso contrário, certifique-se de ter algo em sua função (ou uma chamada de função, STDLbs, etc).Sem recursão simplesmente não seria possível ter coisas como...Google ou SQL, ou qualquer lugar onde seja necessário classificar com eficiência grandes estruturas de dados (classes) ou bancos de dados.
Recursão é o caminho a percorrer, se você quiser iterar através de arquivos, com certeza é assim que 'Find * | ? Grep *'funciona.Meio que uma recursão dupla, especialmente com o pipe (mas não faça um monte de syscalls como muitos gostam de fazer se for algo que você vai disponibilizar para outros usarem).
Linguagens de nível superior e até clang/cpp podem implementá-lo da mesma forma em segundo plano.
