Recursão ou enquanto loops

123

Eu estava lendo sobre algumas práticas de entrevistas de desenvolvimento, especificamente sobre as perguntas e testes técnicos feitos nas entrevistas, e me deparei várias vezes com frases do gênero "Ok, você resolveu o problema com um loop while, agora você pode fazê-lo com recursion "ou" todos podem resolver isso com um loop while de 100 linhas, mas eles podem fazer isso em uma função recursiva de 5 linhas? " etc.

Minha pergunta é: a recursão geralmente é melhor do que se / enquanto / para construções?

Sinceramente, sempre achei que a recursão não é a preferida, porque ela se limita à memória da pilha, que é muito menor que a pilha, também fazer um grande número de chamadas de função / método é abaixo do ideal do ponto de vista do desempenho, mas posso estar errado...

Shivan Dragon
fonte
73
Em matéria de recursão, isso parece bastante interessante.
dan_waterworth
4
@dan_waterworth também, isso ajudaria: google.fr/…, mas sempre pareço soletrar errado : P
Shivan Dragon
@ShivanDragon eu pensava assim ^ _ ^ Muito apropriado que eu postei ontem :-)
Neal
2
Nos ambientes incorporados em que trabalhei em recursão, é desaprovada, na melhor das hipóteses, e você é flagelado publicamente, na pior das hipóteses. O espaço limitado da pilha, na verdade, o torna ilegal.
Fred Thomsen

Respostas:

192

A recursão não é intrinsecamente melhor ou pior que os loops - cada um tem vantagens e desvantagens, e esses até dependem da linguagem de programação (e implementação).

Tecnicamente, os loops iterativos ajustam-se melhor aos sistemas de computador típicos no nível do hardware: no nível do código da máquina, um loop é apenas um teste e um salto condicional, enquanto a recursão (implementada ingenuamente) envolve empurrar um quadro de pilha, pular, retornar e recuar. da pilha. OTOH, muitos casos de recursão (especialmente aqueles que são trivialmente equivalentes a loops iterativos) podem ser escritos para que a pilha push / pop possa ser evitada; isso é possível quando a chamada de função recursiva é a última coisa que acontece no corpo da função antes de retornar e é comumente conhecida como otimização de chamada de cauda (ou otimização de recursão de cauda ). Uma função recursiva otimizada para chamada de cauda adequadamente é equivalente a um loop iterativo no nível do código da máquina.

Outra consideração é que os loops iterativos exigem atualizações de estado destrutivas, o que os torna incompatíveis com a semântica da linguagem pura (sem efeitos colaterais). Essa é a razão pela qual linguagens puras como Haskell não possuem construções de loop, e muitas outras linguagens de programação funcional não as possuem completamente ou as evitam o máximo possível.

Porém, a razão pela qual essas perguntas aparecem tanto nas entrevistas é que, para respondê-las, você precisa de um entendimento completo de muitos conceitos vitais de programação - variáveis, chamadas de função, escopo e, naturalmente, loops e recursão - e você tem trazer a flexibilidade mental para a mesa que permite abordar um problema de dois ângulos radicalmente diferentes e mover-se entre diferentes manifestações do mesmo conceito.

A experiência e a pesquisa sugerem que existe uma linha entre as pessoas que têm a capacidade de entender variáveis, indicadores e recursão e as que não. Quase todo o resto em programação, incluindo estruturas, APIs, linguagens de programação e seus casos extremos, pode ser adquirido através do estudo e da experiência, mas se você não conseguir desenvolver uma intuição para esses três conceitos principais, não poderá ser um programador. Traduzir um loop iterativo simples para uma versão recursiva é a maneira mais rápida possível de filtrar os não programadores - mesmo um programador inexperiente pode fazê-lo em 15 minutos e é um problema muito independente da linguagem, para que o candidato possa escolher uma língua de sua escolha em vez de tropeçar em idiossincrasias.

Se você receber uma pergunta como essa em uma entrevista, é um bom sinal: significa que o possível empregador está procurando pessoas que possam programar, não pessoas que memorizaram o manual de uma ferramenta de programação.

tdammers
fonte
3
Eu gosto mais da sua resposta, porque ela aborda os aspectos mais importantes que uma resposta a essa pergunta poderia ter, explica as principais partes técnicas e também fornece uma boa visão ampliada de como esse problema se encaixa na esfera de programação.
Shivan Dragão
11
Também notei um padrão em uma programação de sincronização em que loops são evitados em favor de chamadas recursivas em um iterador que contém um método .next (). Presumo que ele impede que o código de execução demorada se torne muito voraz na CPU.
Evan Solha
11
A versão iterativa também envolve empurrar e exibir valores. Você só precisa escrever manualmente o código para fazer isso. A versão recursiva está empurrando o estado para a pilha em um algoritmo iterativo, geralmente você precisa simular manualmente empurrando o estado para alguma estrutura. Somente os algoritmos mais triviais não precisam desse estado e, nesses casos, o compilador geralmente pode detectar a recursão da cauda e plantar uma solução iterativa.
Martin York
11
@tdammers Você poderia me dizer onde eu posso ler o estudo que você mencionou "A experiência e a pesquisa sugerem que existe uma linha entre as pessoas ..." Isso parece ser muito interessante para mim.
precisa saber é o seguinte
2
Uma coisa que você esqueceu de mencionar, o código iterativo tende a ter um desempenho melhor quando você está lidando com um único encadeamento de execução, mas os algoritmos recursivos tendem a ser executados em vários encadeamentos.
precisa saber é o seguinte
37

Depende.

  • Alguns problemas são muito propensos a soluções recursivas, por exemplo, quicksort
  • Alguns idiomas não suportam recursão, por exemplo, FORTRANs antigos
  • Algumas linguagens assumem a recursão como principal meio de loop, por exemplo, Haskell

Também vale a pena notar que o suporte à recursão da cauda torna os loops recursivos e iterativos equivalentes, ou seja, a recursão nem sempre precisa desperdiçar a pilha.

Além disso, um algoritmo recursivo sempre pode ser implementado iterativamente usando uma pilha explícita .

Finalmente, eu observaria que uma solução de cinco linhas provavelmente é sempre melhor que uma de 100 linhas (supondo que elas sejam realmente equivalentes).

jk.
fonte
5
Boa resposta (+1). "uma solução de 5 linhas provavelmente é sempre melhor que uma de 100 linhas": acho que concisão não é a única vantagem da recursão. O uso de uma chamada recursiva obriga a tornar explícitas as dependências funcionais entre valores em diferentes iterações.
Giorgio
4
Soluções mais curtas tendem a ser melhores, mas existe algo que é excessivamente conciso.
dan_waterworth
5
@dan_waterworth comparação com "100 line" é bastante difícil de ser excessivamente concisa
mosquito
4
@Giorgio, você pode diminuir os programas removendo códigos desnecessários ou tornando implícitas as coisas explícitas. Contanto que você se atenha ao primeiro, você melhora a qualidade.
dan_waterworth
11
@ jk, acho que é outra forma de tornar implícita a informação explícita. As informações sobre o uso de uma variável são removidas do nome, onde estão explícitas, e são inseridas no uso implícito.
dan_waterworth
17

Não existe uma definição universalmente acordada de "melhor" quando se trata de programação, mas entendo como "mais fácil de manter / ler".

A recursão tem um poder mais expressivo do que as construções de loop iterativo: digo isso porque um loop while é equivalente a uma função recursiva da cauda e as funções recursivas não precisam ser recursivas da cauda. Construções poderosas geralmente são uma coisa ruim porque permitem que você faça coisas difíceis de ler. No entanto, a recursão permite que você escreva loops sem usar a mutabilidade e, na minha opinião, a mutabilidade é muito mais poderosa que a recursão.

Portanto, da baixa potência expressiva à alta potência expressiva, as construções de loop se acumulam da seguinte forma:

  • Funções recursivas de cauda que usam dados imutáveis,
  • Funções recursivas que usam dados imutáveis,
  • Enquanto loops que usam dados mutáveis,
  • Funções recursivas de cauda que usam dados mutáveis,
  • Funções recursivas que usam dados mutáveis,

Idealmente, você usaria as construções menos expressivas que puder. Obviamente, se seu idioma não suportar a otimização de chamada de cauda, ​​isso também poderá influenciar sua escolha de construção de loop.

dan_waterworth
fonte
11
"um loop while é equivalente a uma função recursiva da cauda e funções recursivas não precisam ser recursivas da cauda": +1. Você pode simular a recursão por meio de um loop while + uma pilha.
Giorgio
11
Não tenho certeza se concordo 100%, mas é certamente uma perspectiva interessante, então marque com +1 isso.
Konrad Rudolph
+1 para obter uma ótima resposta e também para mencionar que alguns idiomas (ou compiladores) não fazem otimizações de chamada de cauda.
Shivan Dragon
@Giorgio, "Você pode simular a recursão por meio de um loop while + uma pilha", foi por isso que disse poder expressivo. Computacionalmente, eles são igualmente poderosos.
dan_waterworth
@dan_waterworth: Exatamente, e como você disse em sua resposta, a recursão sozinha é mais expressiva do que um loop while porque você precisa adicionar uma pilha a um loop while para simular a recursão.
Giorgio
7

A recursão costuma ser menos óbvia. Menos óbvio é mais difícil de manter.

Se você escreve for(i=0;i<ITER_LIMIT;i++){somefunction(i);}no fluxo principal, deixa perfeitamente claro que está escrevendo um loop. Se você escreve somefunction(ITER_LIMIT);, não deixa claro o que vai acontecer. Somente vendo conteúdo: as somefunction(int x)chamadas somefunction(x-1)informam que, de fato, é um loop usando iterações. Além disso, você não pode facilmente colocar uma condição de escape em break;algum lugar a meio caminho das iterações; você deve adicionar uma condicional que será transmitida até o fim ou lançar uma exceção. (e as exceções novamente adicionam complexidade ...)

Em essência, se é uma escolha óbvia entre iteração e recursão, faça a coisa intuitiva. Se a iteração executar o trabalho facilmente, poupar 2 linhas raramente valerá as dores de cabeça que pode criar a longo prazo.

É claro que, se estiver economizando 98 linhas, é uma questão totalmente diferente.

Há situações em que a recursão simplesmente se encaixa perfeitamente e elas não são realmente incomuns. Atravessar estruturas de árvores, redes multi-vinculadas, estruturas que podem conter seu próprio tipo, matrizes irregulares multidimensionais, essencialmente qualquer coisa que não seja um vetor direto ou uma matriz de dimensões fixas. Se você percorrer um caminho reto conhecido, itere. Se você mergulhar no desconhecido, recorra.

Essencialmente, se somefunction(x-1)é para ser chamado de dentro de si mais de uma vez por nível, esqueça as iterações.

... Escrever funções iterativamente para tarefas que são melhor executadas por recursão é possível, mas não agradável. Onde quer que você use int, você precisa de algo parecido stack<int>. Fiz isso uma vez, mais como um exercício do que para fins práticos. Posso garantir que, quando enfrentar uma tarefa dessas, não terá dúvidas como as que expressou.

SF.
fonte
10
O que é óbvio e o que é menos óbvio depende parcialmente do que você está acostumado. A iteração tem sido usada com mais frequência nas linguagens de programação, pois é mais próxima da maneira de trabalhar da CPU (ou seja, usa menos memória e executa mais rapidamente). Mas se você está acostumado a pensar indutivamente, a recursão pode ser tão intuitiva.
Giorgio
5
"Se eles virem uma palavra-chave loop, sabem que é um loop. Mas não existe uma palavra-chave recurs, eles podem reconhecê-la apenas vendo f (x-1) dentro de f (x).": Quando você chama uma função recursiva, faz isso não quero saber que é recursivo. Da mesma forma, quando você chama uma função que contém um loop, não deseja saber que ele contém um loop.
Giorgio
3
@SF: Sim, mas você só pode ver isso se observar o corpo da função. No caso de um loop, você vê o loop, em caso de recursão, a função se chama.
Giorgio
5
@SF: Parece um raciocínio circular para mim: "Se, na minha intuição, é um loop, então é um loop". mappode ser definida como uma função recursiva (consulte, por exemplo, haskell.org/tutorial/functions.html ), mesmo que seja intuitivamente claro que ele percorre uma lista e aplica uma função a cada membro da lista.
Giorgio
5
@SF, mapnão é uma palavra-chave, é uma função regular, mas isso é um pouco irrelevante. Quando programadores funcionais usam recursão, geralmente não é porque eles querem executar uma sequência de ações, é porque o problema que está sendo resolvido pode ser expresso como uma função e uma lista de argumentos. O problema pode ser reduzido para outra função e outra lista de argumentos. Eventualmente, você tem um problema que pode ser resolvido trivialmente.
dan_waterworth
6

Como de costume, isso não pode ser respondido em geral porque existem fatores adicionais, que na prática são amplamente desiguais entre casos e desiguais entre si em um caso de uso. Aqui estão algumas das pressões.

  • Código curto e elegante é geralmente superior ao código longo e complexo.
  • No entanto, o último ponto é um pouco invalidado se sua base de desenvolvedores não estiver familiarizada com recursão e não estiver disposta / incapaz de aprender. Pode até se tornar um pouco negativo, e não positivo.
  • A recursão pode prejudicar a eficiência se você precisar de chamadas profundamente aninhadas na prática e não puder usar a recursão de cauda (ou seu ambiente não poderá otimizar a recursão de cauda).
  • A recursão também é ruim em muitos casos se você não conseguir armazenar em cache adequadamente os resultados intermediários. Por exemplo, o exemplo comum de uso da recursão em árvore para calcular números de Fibonacci apresenta um desempenho horrivelmente ruim se você não armazenar em cache. Se você faz cache, é simples, rápido, elegante e totalmente maravilhoso.
  • A recursão não é aplicável a alguns casos, apenas tão boa quanto a iteração em outros e absolutamente necessária em outros. Explorar longas cadeias de regras de negócios geralmente não é ajudado pela recursão. A iteração nos fluxos de dados pode ser útil com recursão. A iteração sobre estruturas dinâmicas multidimensionais de dados (por exemplo, labirintos, árvores de objetos ...) é praticamente impossível sem recursão, explícita ou implícita. Observe que nesses casos, a recursão explícita é muito melhor do que implícita - nada é mais doloroso do que ler código em que alguém implementou sua própria pilha de bugs ad-hoc, incompleta e incompleta no idioma, apenas para evitar a assustadora palavra-R.
Kilian Foth
fonte
O que você quer dizer com cache em relação à recursão?
Giorgio
@Giorgio presumivelmente memoization
jk.
Feh. Se o seu ambiente não otimizar as chamadas finais, você deverá encontrar um ambiente melhor e, se seus desenvolvedores não estiverem familiarizados com a recursão, deverá encontrar melhores desenvolvedores. Tenha alguns padrões, pessoal!
CA McCann
1

A recursão é repetir a chamada à função, o loop é repetir o salto para colocar na memória.

Deve ser mencionado também sobre o estouro de pilha - http://en.wikipedia.org/wiki/Stack_overflow

okobaka
fonte
11
Recursão significa uma função cuja definição implica se chamar.
hardmath
11
Embora sua definição simples não seja exatamente 100% precisa, você é o único que mencionou a pilha em excesso.
Qix
1

Realmente depende da conveniência ou da exigência:

Se você usar a linguagem de programação Python , ela suporta recursão, mas, por padrão, há um limite para a profundidade da recursão (1000). Se exceder o limite, obteremos um erro ou exceção. Esse limite pode ser alterado, mas se fizermos isso, podemos enfrentar situações anormais no idioma.

No momento (número de chamadas além da profundidade da recursão), precisamos preferir construções de loop. Quero dizer, se o tamanho da pilha não for suficiente, temos que preferir as construções de loop.

usernaveen
fonte
3
Aqui está um blog de Guido van Rossum sobre por que ele não quer a otimização da recursão de cauda no Python (apoiando a noção de que diferentes idiomas adotam abordagens táticas distintas).
hardmath
-1

Use o padrão de design da estratégia.

  • A recursão está limpa
  • Os loops são (sem dúvida) eficientes

Dependendo da sua carga (e / ou outras condições), escolha uma.

Pravin Sonawane
fonte
5
Espere o que? Como o padrão de estratégia se encaixa aqui? E a segunda frase parece uma frase vazia.
Konrad Rudolph
@KonradRudolph Gostaria de recursão. Para conjuntos muito grandes de dados, eu mudaria para loops. Foi isso que eu quis dizer. Peço desculpas se não estava claro.
Pravin Sonawane
3
Ah Bem, ainda não tenho certeza de que isso possa ser chamado de "padrão de design da estratégia", que tem um significado muito fixo e você o usa de forma metafórica. Mas agora pelo menos vejo para onde você está indo.
Konrad Rudolph
@KonradRudolph aprendeu uma lição importante. Profundamente explicar o que você quer dizer .. Thanks .. que ajudou .. :)
Pravin Sonawane
2
@ Prin Sonawane: Se você pode usar a otimização da recursão da cauda, ​​também pode usar a recursão em grandes conjuntos de dados.
Giorgio