it-swarm-pt.tech

Recursão ou Iteração?

Existe 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 dada é um palíndromo. Já vi muitos programadores usando a recursão como um meio de mostrar quando um algoritmo de iteração simples pode se encaixar na conta. O compilador desempenha um papel vital ao decidir o que usar?

207
Omnipotent

É possível que a recursão seja mais cara, dependendo se a função recursiva é cauda recursiva (a última linha é chamada recursiva). Recursão de cauda deve ser reconhecida pelo compilador e otimizada 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 faz mais sentido e é o mais claro para o pobre otário (seja você mesmo ou outra pessoa) que precisa manter o código em poucos meses ou anos. Se você se deparar com problemas de desempenho, faça o perfil do seu código e, em seguida, procure otimizar passando para uma implementação iterativa. Você pode querer olhar em memoization e programação dinâmica .

175
Paul Osborne

Loops podem alcançar um ganho de desempenho para o seu programa. A recursão pode alcançar um ganho de desempenho para seu programador. Escolha o que é mais importante na sua situação!

304
Leigh Caldwell

Comparar a recursão à iteração é como comparar uma chave de fenda Phillips a uma chave de fenda de cabeça chata. Para a maior parte você poderia remover qualquer parafuso de cabeça Phillips com uma 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 à maneira como são projetados (sequências de Fibonacci, percorrendo uma estrutura semelhante a uma árvore, etc.). A recursão torna o algoritmo mais sucinto e mais 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 os cálculos caros no momento em que são necessários, em vez de cada vez que o loop é executado.

Isso deve ser o suficiente para você começar. Eu vou desenterrar alguns artigos e exemplos para você também.

Link 1: Haskel vs PHP (Recursão vs Iteração)

Aqui está um exemplo onde o programador teve que processar um grande conjunto de dados usando PHP. Ele mostra como seria fácil lidar com Haskel usando a recursão, mas como PHPnão tinha uma maneira fácil de realizar o mesmo método, ele foi forçado a usar a iteração para obter o resultado.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Link 2: Recursão de masterização

A maior parte da má reputação da recursão vem dos altos custos e da ineficiência em 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 resumiram alguns dos meus pontos-chave:

"A programação recursiva fornece ao programador uma maneira melhor de organizar o código de uma maneira que seja sustentável e logicamente consistente".

https://developer.ibm.com/articles/l-recurs/

Link 3: A recursão é mais rápida que o loop? (Resposta)

Aqui está um link para uma resposta para uma pergunta do stackoverflow que é semelhante à sua. O autor aponta que muitos dos benchmarks associados a recursing ou looping são muito específicos da linguagem. Linguagens imperativas são tipicamente mais rápidas usando um loop e mais lentas com recursão e vice-versa para linguagens funcionais. Eu acho que o ponto principal a tirar deste link é que é muito difícil responder à pergunta em um sentido cego de linguagem agnóstica/situação.

A recursão é cada vez mais rápida que o loop?

76
Swift

A recursão é mais custosa na memória, já que cada chamada recursiva geralmente requer que um endereço de memória seja enviado para a pilha - de modo 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 do que os loops - como quando se trabalha com árvores. Nestes casos, eu recomendaria que se atenha à recursão.

16
Doron Yaacoby

Normalmente, seria de esperar que a penalidade de desempenho se situasse na outra direção. Chamadas recursivas podem levar à construção de quadros extras de pilha; a penalidade por isso varia. Além disso, em algumas linguagens como Python (mais corretamente, em algumas implementações de alguns idiomas ...), é possível executar os limites de pilha com facilidade 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 loops.

Escrever boas funções recursivas pode reduzir um pouco a penalidade de desempenho, supondo que você tenha um compilador que otimize recursões de cauda, ​​etc. (Verifique também se a função é realmente recursiva de cauda - é uma daquelas coisas que muitas pessoas cometem erros em.)

Além dos casos "Edge" (computação de alto desempenho, profundidade de recursão muito grande, etc.), é preferível adotar a abordagem que expresse mais claramente sua intenção, seja bem projetada e seja passível de manutenção. Otimize apenas depois de identificar uma necessidade.

11
zweiterlinde

A recursão é melhor que a iteração para problemas que podem ser divididos em múltiplos , pedaços menores.

Por exemplo, para fazer um algoritmo recursivo de Fibonnaci, você divide fib (n) em fib (n-1) e fib (n-2) e calcula ambas as partes. Iteração só permite repetir uma única função repetidamente.

No entanto, Fibonacci é realmente um exemplo quebrado e eu 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 analisar o nó pai pode ser dividido em vários 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 múltiplos problemas menores, independentes e similares.

8
Ben

Seu desempenho se deteriora ao usar recursão porque chamar um método, em qualquer idioma, implica muita preparação: o código de chamada envia um endereço de retorno, parâmetros de chamada, algumas outras informações de contexto, como registros do processador, podem ser salvos em algum lugar O método chamado posts envia um valor de retorno que é então recuperado pelo chamador e qualquer informação de contexto que tenha sido salva anteriormente será restaurada. a diferença de desempenho entre uma abordagem iterativa e recursiva reside no tempo que essas operações levam.

Do ponto de vista da implementação, você realmente começa a perceber a diferença quando o tempo necessário para lidar com o contexto de chamada é comparável ao tempo que o método leva para ser executado. Se seu método recursivo demorar mais para ser executado, a parte de gerenciamento de contexto de chamada será executada de maneira recursiva, 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, execute iterativo por motivos de eficiência.

7
entzik

Acredito que a recursão de cauda em Java não está otimizada no momento. Os detalhes são espalhados por toda parte this discussão sobre o LtU e os links associados. Ele pode ser um recurso na próxima versão 7, mas aparentemente apresenta certas dificuldades quando combinado com o Stack Inspection, uma vez que certos quadros estariam ausentes. A inspeção de pilha tem sido usada para implementar seu modelo de segurança de baixa granular desde Java 2.

http://lambda-the-ultimate.org/node/13

6
Mike Edwards

Em muitos casos, a recursão é mais rápida devido ao armazenamento em 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 armazenamento em 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 foi dito pelo professor Kevin Wayne (Universidade de Princeton) sobre o curso de algoritmos apresentado no Coursera.

5
Nikunj Banka

Existem muitos casos em que dá uma solução muito mais elegante sobre o método iterativo, o exemplo comum sendo a travessia de uma árvore binária, portanto, não é necessariamente mais difícil de manter. Em geral, as versões iterativas são geralmente um pouco mais rápidas (e durante a otimização podem substituir uma versão recursiva), mas as versões recursivas são mais fáceis de compreender e implementar corretamente.

5
Felix

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);
}

Ao observar esses dois, podemos ver que a recursão é fácil de entender. Mas se não for usado com cuidado, pode ser muito propenso a erros também. Suponha que, se perdermos if (input == 0), o código será executado por algum tempo e terminará geralmente com um estouro de pilha.

5
Harikrishnan

Depende da linguagem. Em Java você deve usar loops. Linguagens funcionais otimizam a recursão.

4
mc

Usando recursão, você está incorrendo no custo de uma chamada de função com 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.

4
MovEaxEsp

A recursão e a iteração dependem da lógica de negócios que você deseja implementar, embora na maioria dos casos ela possa ser usada de forma intercambiável. A maioria dos desenvolvedores faz recursão porque é mais fácil de entender.

4
Warrior

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 uma recursão em si é uma noção derivada em tal sistema). Lambda O cálculo é um sistema fundamental igualmente poderoso, com 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 é, na verdade, muito mais fácil de entender e manter do que um código puramente iterativo, uma vez que a maioria das estruturas de dados é recursiva. É claro que, para acertar, seria necessário uma linguagem com um suporte para funções de alta ordem e fechamentos, pelo menos - para obter todos os combinadores e iteradores padrão de uma maneira simples. Em C++, é claro, soluções recursivas complicadas podem parecer um pouco feias, a menos que você seja um usuário hardcore de FC++ e similares.

3
SK-logic

Se você está apenas interagindo com uma lista, então convenha, iterar.

Algumas outras respostas mencionaram a travessia da árvore (primeiro em profundidade). É realmente um ótimo exemplo, porque é muito comum fazer uma estrutura de dados muito comum. A recursão é extremamente intuitiva para esse problema.

Confira os métodos "find" aqui: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

3
Joe Cheng

Eu acho que na recursão (sem cauda) haveria um impacto no desempenho para alocar uma nova pilha, etc. toda vez que a função fosse chamada (dependendo da linguagem, é claro).

2
metadave

Em C++, se a função recursiva é uma modelo, o compilador tem mais chance de otimizá-la, já que todas as deduções de tipo e instâncias de função ocorrerão em tempo de compilação. Os compiladores modernos também podem inline a função, se possível. Portanto, se usarmos sinalizadores de otimização como -O3 ou -O2 em g++, as recursões poderão ter a chance de serem 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 otimizado (se estiver bem escrito).

No meu caso, eu estava tentando implementar a exponenciação da matriz por meio da quadratura usando objetos da matriz Armadillo, tanto de forma recursiva quanto iterativa. O algoritmo pode ser encontrado aqui ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Minhas funções foram modeladas e eu calculei matrizes 1,000,00012x12 aumentadas para o poder 10. Eu tenho 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

Estes resultados foram obtidos usando o gcc-4.8 com o flag c ++ 11 (-std=c++11) e o Armadillo 6.1 com o Intel mkl. O compilador da Intel também mostra resultados semelhantes.

2
Titas Chanda

Recursão? Por onde eu começo, o wiki diz "é o processo de repetir itens de maneira semelhante"

De volta ao dia, quando eu estava fazendo C, a recursão de C++ era um deus enviado, como "Recursão de cauda". Você também encontrará muitos algoritmos de ordenação usando 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 consiga encontrar um uso imediato ou frequente, mas haverá problemas se ficar satisfeito.

2
Nickz

depende da "profundidade de recursão". isso 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 maneira recursiva é muito ineficiente devido a: - risco de transbordamento de dados - risco de transbordamento de pilha - sobrecarga de chamada de função ocupam 80% do tempo de execução

enquanto o desenvolvimento de um algoritmo min-max para análise de posição no jogo de xadrez que analisará movimentos posteriores N pode ser implementado em recursão sobre a "profundidade de análise" (como eu estou fazendo ^ _ ^)

2
ugasoft

Mike está correto. A recursão de tail é não otimizada 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);
}
1
noah

Recursão tem uma desvantagem que o algoritmo que você escreve usando recursão tem O(n) complexidade de espaço. Embora a abordagem iterativa tenha uma complexidade espacial de O (1). Essa é a vantagem de usar a iteração sobre a recursão. Então, por que usamos recursão?

Ver 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 teria que lidar com a pilha.

1
Varunnuevothoughts

Você deve ter em mente que, utilizando uma recursão muito profunda, você encontrará o Stack Overflow, dependendo do tamanho de pilha permitido. Para evitar isso, certifique-se de fornecer algum caso base que termine a recursão.

1
Grigori A.

Até onde sei, o Perl não otimiza as chamadas recursivas, 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 for chamado pela primeira vez, alocará espaço na pilha. Em seguida, ele irá alterar seus argumentos e reiniciar a sub-rotina, sem acrescentar nada à pilha. Portanto, ele fingirá que nunca chamou a si mesmo, transformando-o em um processo iterativo.

Observe que não há "my @_;" ou "local @_;", se você fez isso não funcionaria mais.

0
Brad Gilbert

Se as iterações são atômicas e ordens de magnitude mais caras do que empurrar um novo quadro de pilha e criando um novo tópico e você tem múltiplos núcleos e seu O ambiente de tempo de execução pode usar todos eles e, em seguida, uma abordagem recursiva poderia 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 conjunto de encadeamentos que controlará a alocação de encadeamentos e evitará que seu processo crie muitos encadeamentos e monopolize o sistema.

Por exemplo, em alguns idiomas, existem implementações de classificação de mesclagem multithreads recursivas.

Mas, novamente, o multithreading pode ser usado com loop em vez de recursão, portanto, como essa combinação funcionará depende de mais fatores, incluindo o sistema operacional e seu mecanismo de alocação de encadeamentos.

0
ccpizza

Usando apenas Chrome 45.0.2454.85 m, a recursão parece ser uma boa quantia 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 é executado usando o padrão para loop

100x para execução de loop. Hora de completar: 7.683ms

// 100 execuções usando abordagem recursiva funcional com recursão de cauda

Corrida de recursão de 100x. Tempo para concluir: 4.841ms

Na captura de tela abaixo, a recursão ganha novamente por uma margem maior quando executada em 300 ciclos por teste

Recursion wins again!

0
Alpha G33k