Recursão ou while loops

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

Tecnicamente, loops iterativos ajustam sistemas de computadores típicos melhor no nível de hardware: no nível de código de máquina, um loop é apenas um teste e um salto condicional, enquanto recursão (implementada ingenuamente) envolve empurrar um quadro de pilha, saltar, retornar, e voltando da pilha. OTOH, muitos casos de recursão (especialmente aqueles que são trivialmente equivalentes a loops iterativos) podem ser escritos para que o empilhamento / pop da pilha possa ser evitado; 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 da chamada final (ou otimização da recursão da cauda ) . Uma função recursiva otimizada de chamada de cauda é, na maioria das vezes, equivalente a um loop iterativo no nível de código da máquina.

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

O motivo pelo qual essas perguntas aparecem tanto em entrevistas, porém, é que, para respondê-las, você precisa de um conhecimento profundo de muitos conceitos vitais de programação - variáveis, chamadas de função, escopo e, é claro, loops e recursão -, e você tem que trazer a flexibilidade mental para a mesa que permite abordar um problema a partir 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 pessoas que têm a capacidade de entender variáveis, ponteiros e recursividade e aquelas que não têm. Quase tudo o mais em programação, incluindo frameworks, APIs, linguagens de programação e seus casos de ponta, pode ser adquirido através do estudo e da experiência, mas se você não for capaz de desenvolver uma intuição para esses três conceitos básicos, estará incapacitado para ser um programador. A tradução de um loop iterativo simples em uma versão recursiva é a maneira mais rápida de filtrar os não-programadores - até mesmo um programador bastante inexperiente pode fazer isso em 15 minutos, e é um problema muito agnóstico de linguagem, então o candidato pode escolher uma linguagem de sua escolha, em vez de tropeçar em idiossincrasias.

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

    

Depende.

• Alguns problemas são muito receptivos a soluções recursivas, por ex. quicksort
• Algumas línguas não suportam realmente a recursão, por ex. primeiros FORTRANs
• Algumas linguagens consideram a recursão como um meio primário de loop, por ex. Haskell

Também vale a pena notar que o suporte para a recursão final torna a repetição recursiva e os loops iterativos equivalentes, ou seja, a recursão não t sempre tem que desperdiçar a pilha.

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

Finalmente, eu notaria que uma solução de cinco linhas provavelmente é sempre melhor do que uma de 100 linhas (assumindo que elas são realmente equivalentes).

    

Não há uma definição universalmente aceita de "melhor" quando se trata de programação, mas vou dizer que é "mais fácil de manter / ler".

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

Assim, de baixa potência expressiva a alta potência expressiva, as construções de loop se acumulam assim:

• Funções recursivas de cauda que usam dados imutáveis,
• Funções recursivas que usam dados imutáveis,
• While 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 possíveis. É claro que, se o seu idioma não suportar otimização de chamada final, isso também pode influenciar sua escolha de construção em loop.

    

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

Se você escrever for(i=0;i<ITER_LIMIT;i++){somefunction(i);} no fluxo principal, você deixará perfeitamente claro que está escrevendo um loop. Se você escrever somefunction(ITER_LIMIT); você não deixa claro o que vai acontecer. Somente ver conteúdo: que somefunction(int x) chama somefunction(x-1) indica que, na verdade, é um loop usando iterações. Além disso, você não pode facilmente colocar uma condição de escape com break; em algum lugar na metade das iterações, você deve adicionar uma condicional que será passada totalmente ou lançar uma exceção. (e 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 faz o trabalho facilmente, economizar 2 linhas raramente vale a pena as dores de cabeça que pode criar no longo prazo.

Claro que se você economizar 98 linhas, isso é um assunto totalmente diferente.

Existem situações para as quais a recursão simplesmente se encaixa perfeitamente e elas não são realmente incomuns. Traversal de estruturas de árvores, redes com múltiplas ligações, estruturas que podem conter seu próprio tipo, matrizes recortadas multidimensionais, essencialmente qualquer coisa que não seja um vetor direto ou uma matriz de dimensões fixas. Se você percorrer um caminho conhecido e reto, itere. Se você mergulhar em desconhecido, recurse.

Essencialmente, se somefunction(x-1) for chamado de dentro de si mesmo 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 como stack<int> . Eu fiz isso uma vez, mais como um exercício do que para propósitos práticos. Posso garantir que, assim que você enfrentar essa tarefa, não terá dúvidas como as que expressou.

    

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

• O código curto e elegante é geralmente superior ao código longo e complexo.
• No entanto, o último ponto é um pouco invalidado se a sua base de desenvolvedores não estiver familiarizada com a recursão e sem vontade / incapaz de aprender. Pode até se tornar um ligeiro negativo em vez de positivo.
• A recursão pode ser ruim para a eficiência se você precisar de chamadas profundamente aninhadas na prática e você não pode usar a recursão da cauda (ou seu ambiente não pode otimizar a cauda recursão).
• A recursão também é ruim em muitos casos, se você não puder armazenar corretamente os resultados intermediários. Por exemplo, o exemplo comum de usar a recursão de árvore para computar números de Fibonacci executa terrivelmente ruim se você não fizer o cache. Se você faz cache, é simples, rápido, elegante e totalmente maravilhoso.
• A recursão não é aplicável a alguns casos, tão boa quanto a iteração em outros e absolutamente necessária em outros. Investir em longas cadeias de regras de negócios geralmente não é ajudado pela recursão. A iteração por meio de fluxos de dados pode ser feita de maneira útil com recursão. Iterar sobre estruturas de dados dinâmicas multidimensionais (por exemplo, labirintos, árvores de objetos ...) é praticamente impossível sem recursividade, explícita ou implícita. Note que nesses casos, a recursão explícita é muito melhor que implícita - nada é mais doloroso do que ler código onde alguém implementou sua própria pilha ad-hoc, incompleta e com bugs dentro da linguagem apenas para evitar o R assustador. palavra-chave.

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

Deve ser mencionado também sobre estouro de pilha - link

    

Depende realmente da conveniência ou do requisito:

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

Neste momento (número de chamadas mais do que a profundidade de recursão), precisamos preferir construções de loop. Quer dizer, se o tamanho da pilha não for suficiente, temos que preferir as construções de loop.

    

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

• A recursão é limpa
• Os loops são (possivelmente) eficientes

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