Quais são as considerações para determinar se você pode usar a recursão para resolver um problema?

Às vezes, nas entrevistas, posso usar a recursão para resolver um problema (como adicionar 1a um número inteiro de precisão infinita) ou quando o problema se apresenta adequado para usar a recursão. Às vezes, pode ser apenas devido ao uso muito da recursão para a solução de problemas; portanto, sem pensar muito, a recursão é usada para resolver o problema.

No entanto, quais são as considerações antes de decidir que é adequado usar a recursão para resolver um problema?

Alguns pensamentos que tive:

Se usarmos recursão em dados que são cortados pela metade todas as vezes, parece que não há problema em usar recursão, pois todos os dados que podem caber em 16 GB de RAM ou até um disco rígido de 8 TB podem ser manipulados por recursão com apenas 42 níveis de profundidade. (portanto, não há excesso de pilha (acho que em alguns ambientes, a pilha pode ter 4000 níveis de profundidade, muito mais que 42, mas, ao mesmo tempo, também depende de quantas variáveis ​​locais você possui, pois cada pilha de chamadas) ocupa mais memória se houver muitas variáveis ​​locais e o tamanho da memória, e não o nível, determinar o estouro da pilha)).

Se você calcular números de Fibonacci usando recursão pura, precisará se preocupar com a complexidade do tempo, a menos que armazene em cache os resultados intermediários.

E que tal adicionar 1a um número inteiro de precisão infinita? Talvez seja discutível, pois você trabalhará com números com 3000 dígitos ou 4000 dígitos, tão grandes que podem causar um estouro de pilha? Eu não pensei nisso, mas talvez a resposta seja não, não devemos usar recursão, mas apenas um loop simples, porque e se em alguma aplicação, o número realmente precisa ter 4000 dígitos, para verificar se há algum propriedades do número, como se o número é primo ou não.

A questão final é: quais são as considerações antes que você possa decidir usar a recursão para resolver um problema?

Uma consideração é se o seu algoritmo pretende ser uma solução abstrata ou uma solução executável prática. No primeiro caso, os atributos que você procura são correção e facilidade de entendimento para seu público-alvo ¹ . Neste último caso, o desempenho também é um problema. Essas considerações podem influenciar sua escolha.

Uma segunda consideração (para uma solução prática) é se a linguagem de programação (ou mais estritamente, sua implementação) que você está usando faz a eliminação da chamada de cauda? Sem eliminação da chamada de cauda, ​​a recursão é mais lenta que a iteração e a recursão profunda pode levar a problemas de estouro da pilha.

Observe que uma solução recursiva (correta) pode ser transformada em uma solução não recursiva equivalente, portanto, você não precisa fazer uma escolha difícil entre as duas abordagens.

Finalmente, às vezes a escolha entre formulações recursivas e não recursivas é motivada pela necessidade de provar (no sentido formal) propriedades sobre um algoritmo. As formulações recursivas permitem mais diretamente a prova por indução.

^{1 - Isso inclui considerações como se o público-alvo ... e isso pode incluir programadores que leem código prático ... veriam um estilo de solução como "mais natural" que o outro. A noção de "natural" variará de pessoa para pessoa, dependendo de como eles aprenderam programação ou algoritmos. (Desafio qualquer pessoa que propõe a "naturalidade" como o principal critério para decidir usar a recursão (ou não) para definir a "naturalidade" em termos objetivos; ou seja, como você a avaliaria.)}

Como programador de C / C ++, minha principal consideração é o desempenho. Meu processo de decisão é algo como:

1. Qual é a profundidade máxima da pilha de chamadas? Se for muito profundo, livre-se da recursão. Se raso, vá para 2.

2. É provável que essa função seja um gargalo do meu programa? Se sim, vá para 3. Se não, mantenha a recursão. Se não tiver certeza, execute um criador de perfil.

3. Qual é a fração do tempo de CPU gasto em chamadas de função recursivas? Se as chamadas de função demorarem significativamente menos que o resto do corpo da função, não há problema em usar recursão.

No entanto, quais são as considerações antes de decidir que é adequado usar a recursão para resolver um problema?

Ao escrever funções no Scheme, acho natural escrever funções recursivas de cauda sem pensar muito.

Ao escrever funções em C ++, encontro-me debatendo antes de usar uma função recursiva. As perguntas que me faço são:

• A computação pode ser realizada usando um algoritmo iterativo? Se sim, use uma abordagem iterativa.

• A profundidade da recursão pode aumentar pelo tamanho do modelo? Recentemente, deparei-me com um caso em que a profundidade da recursão aumentou para quase 13.000 devido ao tamanho do modelo. Eu tive que converter a função para usar um algoritmo iterativo pós-acelerada.

  Por esse motivo, eu não recomendaria escrever um algoritmo de passagem em árvore usando funções recursivas. Você nunca sabe quando a árvore se torna muito profunda para o seu ambiente de tempo de execução.

• A função pode ficar muito complicada usando um algoritmo iterativo? Se sim, use uma função recursiva. Não tentei escrever qsortusando uma abordagem iterativa, mas sinto que usar uma função recursiva é mais natural para ela.

Para números de Fibonacci, a ingênua "recursão" é totalmente estúpida. Isso porque leva ao mesmo subproblema sendo resolvido repetidamente.

Na verdade, existe uma variação trivial dos números de Fibonacci, onde a recursão é muito eficiente: dado um número n ≥ 1, calcule fib (n) e fib (n-1). Então você precisa de uma função que retorne dois resultados, vamos chamar essa função fib2.

A implementação é bastante simples:

function fib2 (n) -> (fibn, fibnm1) {
    if n ≤ 1 { return (1, 1) }
    let (fibn, fibnm1) = fib2 (n-1)
    return (fibn + fibnm1, fibn)
}