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...
fonte
Respostas:
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.
fonte
Depende.
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).
fonte
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:
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.
fonte
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ê escrevesomefunction(ITER_LIMIT);
, não deixa claro o que vai acontecer. Somente vendo conteúdo: assomefunction(int x)
chamadassomefunction(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 embreak;
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 parecidostack<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.fonte
map
pode 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.map
nã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.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.
fonte
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
fonte
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.
fonte
Use o padrão de design da estratégia.
Dependendo da sua carga (e / ou outras condições), escolha uma.
fonte