Existe um impacto no desempenho se usarmos um loop em vez de recursão ou vice-versa em algoritmos em que ambos podem servir ao mesmo propósito? Por exemplo: verifique se a sequência fornecida é um palíndromo. Eu já vi muitos programadores usando a recursão como um meio de mostrar quando um algoritmo de iteração simples pode ser adequado. O compilador desempenha um papel vital na decisão do que usar?

É possível que a recursão seja mais cara, dependendo se a função recursiva for recursiva de cauda (a última linha é chamada recursiva). A recursão de cauda deve ser reconhecida pelo compilador e otimizada para sua contraparte iterativa (mantendo a implementação clara e concisa que você possui em seu código).

Eu escreveria o algoritmo da maneira que faz mais sentido e é a mais clara para o pobre otário (seja você ou outra pessoa) que precisa manter o código em alguns meses ou anos. Se você tiver problemas de desempenho, crie um perfil do seu código e, então, e somente então, procure otimizar, passando para uma implementação iterativa. Você pode querer examinar memoização e programação dinâmica .

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

Comparar recursão a iteração é como comparar uma chave de fenda Phillips com uma chave de fenda. Na maioria das vezes, você pode remover qualquer parafuso 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 se prestam à recursão devido à maneira como são projetados (sequências de Fibonacci, atravessando uma árvore como estrutura etc.). A recursão torna o algoritmo mais sucinto e fácil de entender (portanto compartilhável e reutilizável).

Além disso, alguns algoritmos recursivos usam "Lazy Evaluation", que os torna mais eficientes do que seus irmãos iterativos. Isso significa que eles só fazem os cálculos dispendiosos no momento em que são necessários, em vez de cada vez que o loop é executado.

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

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

Aqui está um exemplo em que o programador teve que processar um grande conjunto de dados usando PHP. Ele mostra como seria fácil lidar com Haskel usando recursão, mas como o PHP nã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: Dominando a recursão

A maior parte da má reputação da recursão vem dos altos custos e da ineficiência em idiomas imperativos. 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 do uso da recursão final. Suas palavras finais realmente resumiram alguns dos meus pontos-chave, eu acho:

"a programação recursiva oferece ao programador uma maneira melhor de organizar o código de uma maneira que seja ao mesmo tempo mantida e logicamente consistente".

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

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

Aqui está um link para uma resposta para uma pergunta de fluxo de pilha semelhante à sua. O autor ressalta que muitos dos benchmarks associados à recorrência ou loop são muito específicos do idioma. Linguagens imperativas são geralmente mais rápidas usando um loop e mais lentas com recursão e vice-versa para linguagens funcionais. Acho que o ponto principal a partir desse link é que é muito difícil responder à pergunta em um sentido agnóstico / cego de linguagem.

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

A recursão é mais cara na memória, pois cada chamada recursiva geralmente exige que um endereço de memória seja enviado à pilha - para que mais tarde o programa possa retornar a esse ponto.

Ainda assim, existem muitos casos em que a recursão é muito mais natural e legível que os loops - como quando se trabalha com árvores. Nesses casos, eu recomendaria manter a recursão.

Normalmente, seria de esperar que a penalidade de desempenho estivesse na outra direção. Chamadas recursivas podem levar à construção de quadros de pilha extras; a penalidade para isso varia. Além disso, em algumas linguagens como Python (mais corretamente, em algumas implementações de algumas linguagens ...), você pode executar limites de pilha com bastante facilidade para tarefas especificadas 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 otimiza recursões de cauda, ​​etc. em.)

Além dos casos "avançados" (computação de alto desempenho, profundidade de recursão muito grande etc.), é preferível adotar a abordagem que mais claramente expressa sua intenção, é bem projetada e pode ser mantida. Otimize somente após identificar uma necessidade.

A recursão é melhor que a iteração para problemas que podem ser divididos em várias partes menores.

Por exemplo, para criar um algoritmo recursivo de Fibonnaci, você divide fib (n) em fib (n-1) e fib (n-2) e calcula as duas partes. A iteração permite repetir uma única função repetidamente.

No entanto, Fibonacci é na verdade um exemplo quebrado e 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 um do outro.

Então sim - a recursão é melhor do que a iteração para problemas que podem ser divididos em vários problemas menores, independentes e similares.

Seu desempenho se deteriora ao usar a recursão porque chamar um método, em qualquer idioma, implica muita preparação: o código de chamada publica um endereço de retorno, parâmetros de chamada, algumas outras informações de contexto, como registros do processador, podem ser salvas em algum lugar e, no retorno, O método chamado lança um valor de retorno que é recuperado pelo chamador e qualquer informação de contexto que foi salva anteriormente será restaurada. a diferença de desempenho entre uma abordagem iterativa e uma 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 que leva para lidar com o contexto de chamada é comparável ao tempo que leva para a execução do seu método. Se o seu método recursivo demorar mais para ser executado, a parte de gerenciamento de contexto de chamada será feita de forma 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, seja iterativo por razões de eficiência.

Acredito que a recursão da cauda em java não esteja otimizada no momento. Os detalhes estão espalhados por toda esta discussão no LtU e nos links associados. Ele pode ser um recurso na próxima versão 7, mas, aparentemente, ele apresenta certas dificuldades quando combinados com inspeção da pilha uma vez que certos quadros estaria faltando. O Stack Inspection tem sido usado para implementar seu modelo de segurança refinado desde o Java 2.

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

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

A 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 usando a função recursiva

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

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

Em muitos casos, a recursão é mais rápida devido ao cache, o que melhora o desempenho. Por exemplo, aqui está uma versão iterativa da classificação de mesclagem usando a rotina de mesclagem tradicional. A execução será mais lenta que a implementação recursiva devido ao desempenho aprimorado do 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 o professor Kevin Wayne (Universidade de Princeton) falou sobre o curso de algoritmos apresentado no Coursera.

Usando a recursão, você está incorrendo no custo de uma chamada de função a cada "iteração", enquanto que com um loop, a única coisa que você costuma pagar é 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.

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 busca recursão porque é mais fácil de entender.

Depende do idioma. Em Java, você deve usar loops. Linguagens funcionais otimizam a recursão.

Se você estiver apenas repetindo uma lista, com certeza, repita.

Algumas outras respostas mencionaram (em profundidade) a travessia de árvores. É realmente um exemplo tão bom, porque é uma coisa muito comum de se fazer com 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

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-complete com apenas um par de combinadores (sim, mesmo uma recursão em si é uma noção derivada nesse sistema). O cálculo Lambda é um sistema fundamental igualmente poderoso, com funções recursivas. Mas se você deseja definir uma iteração corretamente, precisará de muito mais primitivas para começar.

Quanto ao código - não, o código recursivo é de fato muito mais fácil de entender e manter do que o puramente iterativo, pois a maioria das estruturas de dados é recursiva. É claro que, para acertar, seria necessário um idioma com suporte para funções e fechamentos de alta ordem, pelo menos - para obter todos os combinadores e iteradores padrão de maneira organizada. No C ++, é claro, soluções recursivas complicadas podem parecer um pouco feias, a menos que você seja um usuário hardcore do FC ++ e similares.

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

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

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

Recursão? Por onde começar, o wiki dirá "é o processo de repetir itens de maneira semelhante"

No dia em que eu fazia C, a recursão em C ++ era um deus, coisas como "recursão em cauda". Você também encontrará muitos algoritmos de classificação que usam 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 encontre um uso imediato ou com frequência, mas haverá um problema, você ficará feliz por ele estar disponível.

No C ++, se a função recursiva for modelada, o compilador terá mais chances de otimizá-la, pois todas as deduções de tipo e instanciações de função ocorrerão em tempo de compilação. Compiladores modernos também podem incorporar a função, se possível. Portanto, se alguém usar sinalizadores de otimização como -O3ou -O2dentro g++, as recursões podem ter a chance de ser mais rápidas que as iterações. Nos códigos iterativos, o compilador tem menos chance de otimizá-lo, pois já está no estado mais ou menos ideal (se escrito bem o suficiente).

No meu caso, eu estava tentando implementar a exponenciação da matriz ao quadrado usando objetos da matriz do Tatu, de maneira recursiva e iterativa. O algoritmo pode ser encontrado aqui ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Minhas funções foram modeladas e calculei 1,000,000 12x12matrizes elevadas ao poder 10. Eu obtive 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

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

Mike está correto. A recursão de cauda não é otimizada pelo compilador Java ou pela JVM. Você sempre terá um estouro de pilha com algo como isto:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Você deve ter em mente que, utilizando recursões muito profundas, você encontrará o Stack Overflow, dependendo do tamanho permitido da pilha. Para evitar isso, certifique-se de fornecer um caso base que encerre sua recursão.

A recursão tem uma desvantagem de que o algoritmo que você escreve usando a recursão possui complexidade de espaço O (n). 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 a iteração. Nesse caso, se você optar por seguir a abordagem de iteração, precisará manipular a pilha sozinho.

Se as iterações forem atômicas e ordens de magnitude mais caras do que empurrar um novo quadro de pilha e criar um novo encadeamento e você tiver vários núcleos e seu ambiente de tempo de execução puder usar todos eles, uma abordagem recursiva poderá 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 sobrecarregue o sistema.

Por exemplo, em alguns idiomas, há implementações recursivas de classificação de mesclagem multithread.

Porém, novamente, o multithreading pode ser usado com loop em vez de recursão, portanto, o quão bem essa combinação funcionará depende de mais fatores, incluindo o SO e seu mecanismo de alocação de encadeamento.

Até onde eu sei, o Perl não otimiza as chamadas recursivas de cauda, ​​mas você pode falsificá-las.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

Quando chamado pela primeira vez, alocará espaço na pilha. Em seguida, ele altera seus argumentos e reinicia a sub-rotina, sem adicionar mais nada à pilha. Portanto, fingirá que nunca se auto denominou, transformando-o em um processo iterativo.

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

Usando apenas o Chrome 45.0.2454.85 m, a recursão parece ser muito 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 execuções usando o padrão para loop

100x para execução em loop. Tempo para conclusão: 7.683ms

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

100x recursão. Tempo para conclusão: 4.841ms

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

Eu encontrei outras diferenças entre essas abordagens. Parece simples e sem importância, mas tem um papel muito importante enquanto você se prepara para entrevistas e esse assunto surge, portanto, preste atenção.

Resumindo: 1) o percurso iterativo de pós-encomenda não é fácil - isso torna a DFT mais complexa 2) os ciclos de verificação mais fácil com recursão

Detalhes:

No caso recursivo, é fácil criar percursos anteriores e posteriores:

Imagine uma pergunta bastante padrão: "imprima todas as tarefas que devem ser executadas para executar a tarefa 5, quando as tarefas dependem de outras tarefas"

Exemplo:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Observe que a passagem pós-ordem recursiva não requer uma reversão subsequente do resultado. Filhos impressos primeiro e sua tarefa na pergunta impressa por último. Tudo está bem. Você pode fazer um percurso de pré-ordem recursiva (também mostrado acima) e esse exigirá uma reversão da lista de resultados.

Não é tão simples com abordagem iterativa! Na abordagem iterativa (uma pilha), você só pode fazer um percurso de pré-encomenda, portanto, você deve reverter a matriz de resultados no final:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Parece simples, não?

Mas é uma armadilha em algumas entrevistas.

Significa o seguinte: com a abordagem recursiva, você pode implementar o Depth First Traversal e selecionar a ordem em que deseja pré ou pós (simplesmente alterando o local da "impressão", no nosso caso, "adicionando à lista de resultados" ) Com a abordagem iterativa (uma pilha), você pode facilmente fazer a pré-encomenda do percurso e, portanto, na situação em que as crianças precisam ser impressas primeiro (praticamente todas as situações em que você precisa começar a imprimir nos nós inferiores, subindo) - você está em o problema. Se você tiver esse problema, poderá reverter mais tarde, mas será uma adição ao seu algoritmo. E se um entrevistador estiver olhando para o relógio, pode ser um problema para você. Existem maneiras complexas de fazer um percurso iterativo de pós-ordem, elas existem, mas não são simples . Exemplo:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Assim, o ponto principal: eu usaria recursão durante as entrevistas, é mais simples de gerenciar e explicar. Você tem uma maneira fácil de percorrer a travessia pré e pós-encomenda em qualquer caso urgente. Com iterativo, você não é tão flexível.

Eu usaria a recursão e diria: "Ok, mas iterativo pode me fornecer um controle mais direto sobre a memória usada, posso medir facilmente o tamanho da pilha e desaprovar algum estouro perigoso .."

Outra vantagem da recursão - é mais simples evitar / observar ciclos em um gráfico.

Exemplo (pré-código):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Pode ser divertido escrevê-lo como recursão ou como prática.

No entanto, se o código for usado na produção, é necessário considerar a possibilidade de estouro de pilha.

A otimização da recursão da cauda pode eliminar o estouro da pilha, mas você deseja enfrentar o problema de fazê-lo e precisa saber que pode contar com a otimização do ambiente.

Sempre que o algoritmo se repete, qual é o tamanho dos dados ou nreduzido em?

Se você estiver reduzindo o tamanho dos dados ou npela metade toda vez que recorrer, geralmente não precisará se preocupar com o estouro da pilha. Digamos, se ele precisa ter 4.000 níveis de profundidade ou 10.000 de profundidade para o programa empilhar em excesso, o tamanho dos dados precisa ser de aproximadamente ^2.000 para que o programa empilhe o excesso. Para colocar isso em perspectiva, um maior dispositivo de armazenamento recentemente pode conter 2 ⁶¹ bytes e, se você tiver 2 ⁶¹ desses dispositivos, estará lidando apenas com 2 ¹²² tamanhos de dados. Se você estiver olhando para todos os átomos do universo, estima-se que ele seja menor que 2 ⁸⁴. Se você precisar lidar com todos os dados do universo e seus estados a cada milissegundo desde que o nascimento do universo foi estimado em 14 bilhões de anos atrás, pode ser apenas 2 ¹⁵³ . Portanto, se o seu programa puder manipular ^2.000 unidades de dados ou n, você poderá manipular todos os dados do universo e o programa não sobrecarregará a pilha. Se você não precisa lidar com números tão grandes quanto 2 ⁴⁰⁰⁰ (um número inteiro de 4000 bits), em geral, não precisa se preocupar com o estouro de pilha.

No entanto, se você reduzir o tamanho dos dados ou nem uma quantidade constante toda vez que recorrer, poderá executar um estouro de pilha quando o programa for executado bem quando nestiver, 1000mas em alguma situação, quando nse tornar apenas 20000.

Portanto, se você tiver a possibilidade de estouro de pilha, tente torná-lo uma solução iterativa.

Vou responder sua pergunta projetando uma estrutura de dados Haskell por "indução", que é uma espécie de "dual" à recursão. E então mostrarei como essa dualidade leva a coisas boas.

Introduzimos um tipo para uma árvore simples:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

Podemos ler esta definição dizendo: "Uma árvore é um ramo (que contém duas árvores) ou é uma folha (que contém um valor de dados)". Portanto, a folha é uma espécie de caso mínimo. Se uma árvore não é uma folha, deve ser uma árvore composta contendo duas árvores. Estes são os únicos casos.

Vamos fazer uma árvore:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Agora, vamos supor que queremos adicionar 1 a cada valor na árvore. Podemos fazer isso chamando:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

Primeiro, observe que essa é de fato uma definição recursiva. Leva os construtores de dados Branch e Leaf como casos (e como o Leaf é mínimo e esses são os únicos possíveis), temos certeza de que a função será encerrada.

O que seria necessário para escrever addOne em um estilo iterativo? Como será o looping em um número arbitrário de ramificações?

Além disso, esse tipo de recursão geralmente pode ser fatorado, em termos de um "functor". Podemos transformar Árvores em Functors definindo:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

e definindo:

addOne' = fmap (+1)

Podemos fatorar outros esquemas de recursão, como o catamorfismo (ou dobra) para um tipo de dados algébrico. Usando um catamorfismo, podemos escrever:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

O estouro de pilha só ocorrerá se você estiver programando em um idioma que não possui gerenciamento de memória incorporado .... Caso contrário, verifique se você tem algo em sua função (ou uma chamada de função, STDLbs, etc). Sem recursão, simplesmente não seria possível ter coisas como ... Google ou SQL, ou qualquer lugar em que se deva classificar com eficiência por meio de grandes estruturas de dados (classes) ou bancos de dados.

A recursão é o caminho a percorrer se você deseja percorrer os arquivos, com certeza é assim que 'find * | ? grep * 'funciona. Meio recursão dupla, especialmente com o pipe (mas não faça um monte de syscalls como muitos gostam de fazer se for algo que você vai colocar lá fora para outros usarem).

Linguagens de nível superior e até clang / cpp podem implementá-lo da mesma forma em segundo plano.