Quais são os problemas do mundo real em que uma abordagem recursiva é a solução natural, além da pesquisa em profundidade (DFS)?

(Não considero a Torre de Hanói , o número de Fibonacci ou os problemas fatoriais do mundo real. Eles são um pouco inventados em minha mente.)

Existem muitos exemplos matemáticos aqui, mas você queria um exemplo do mundo real , então, com um pouco de reflexão, este é possivelmente o melhor que posso oferecer:

Você encontra uma pessoa que contraiu uma determinada infecção contagiosa, que não é fatal, e se corrige rapidamente (Tipo A), exceto uma em cada 5 pessoas (chamaremos de tipo B) que se infectou permanentemente com ela e não mostra sintomas e apenas atua como um propagador.

Isso cria ondas de destruição bastante irritantes sempre que o tipo B infecta uma multidão de tipo A.

Sua tarefa é rastrear todos os tipos B e imunizá-los para interromper a espinha dorsal da doença. Infelizmente, você não pode administrar uma cura nacional para todos, porque as pessoas que são do tipo A também são mortalmente alérgicas à cura que funciona para o tipo B.

A forma como você faria isso, seria a descoberta social, dado uma pessoa infectada (Tipo A), escolher todos os seus contatos na última semana, marcando cada contato em um heap. Quando você testa uma pessoa infectada, adicione-a à fila de "acompanhamento". Quando uma pessoa é do tipo B, adicione-a ao "acompanhamento" na cabeça (porque você deseja interromper isso rapidamente).

Depois de processar uma determinada pessoa, selecione a pessoa na frente da fila e aplique a imunização, se necessário. Obtenha todos os seus contatos não visitados anteriormente e, em seguida, teste para ver se eles estão infectados.

Repita até que a fila de pessoas infectadas chegue a 0 e aguarde outro surto.

(Ok, isso é um pouco iterativo, mas é uma maneira iterativa de resolver um problema recursivo, neste caso, a primeira travessia de uma base populacional tentando descobrir caminhos prováveis ​​para os problemas e, além disso, as soluções iterativas são frequentemente mais rápidas e eficazes , e eu compulsivamente removo a recursão em todos os lugares a ponto de se tornar instintivo. ... droga!)

Um exemplo do mundo real de recursão

Que tal qualquer coisa envolvendo uma estrutura de diretório no sistema de arquivos. Localização recursiva de arquivos, exclusão de arquivos, criação de diretórios, etc.

Aqui está uma implementação Java que imprime recursivamente o conteúdo de um diretório e seus subdiretórios.

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Quicksort , merge sort e a maioria das outras classificações N-log N.

O exemplo de Matt Dillard é bom. De modo mais geral, qualquer caminhada em uma árvore pode geralmente ser tratada por recursão com muita facilidade. Por exemplo, compilar árvores de análise, percorrer XML ou HTML, etc.

A recursão é freqüentemente usada em implementações do algoritmo Backtracking . Para uma aplicação "no mundo real" disso, que tal um solucionador de Sudoku ?

A recursão é apropriada sempre que um problema pode ser resolvido dividindo-o em subproblemas, que podem usar o mesmo algoritmo para resolvê-los. Algoritmos em árvores e listas ordenadas são um ajuste natural. Muitos problemas em geometria computacional (e jogos 3D) podem ser resolvidos recursivamente usando árvores de particionamento de espaço binário (BSP), subdivisões de gordura ou outras maneiras de dividir o mundo em subpartes.

A recursão também é apropriada quando você está tentando garantir a exatidão de um algoritmo. Dada uma função que recebe entradas imutáveis ​​e retorna um resultado que é uma combinação de chamadas recursivas e não recursivas nas entradas, geralmente é fácil provar que a função está correta (ou não) usando indução matemática. Freqüentemente, é difícil fazer isso com uma função iterativa ou com entradas que podem sofrer mutação. Isso pode ser útil ao lidar com cálculos financeiros e outras aplicações onde a correção é muito importante.

Certamente, muitos compiladores por aí usam muito a recursão. As linguagens de computador são inerentemente recursivas (ou seja, você pode incorporar declarações 'if' dentro de outras declarações 'if', etc.).

Desabilitando / configurando somente leitura para todos os controles filhos em um controle de contêiner. Eu precisava fazer isso porque alguns dos controles filhos eram eles próprios contêineres.

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

Ciclo de avaliação / aplicação famoso do SICP

_{(fonte: mit.edu )}

Aqui está a definição de eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

Aqui está a definição de aplicar:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

Aqui está a definição de eval-sequence:

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval-> apply-> eval-sequence->eval

A recursão é usada em coisas como árvores BSP para detecção de colisão no desenvolvimento de jogos (e outras áreas semelhantes).

As pessoas geralmente classificam pilhas de documentos usando um método recursivo. Por exemplo, imagine que você está classificando 100 documentos com nomes. Primeiro coloque os documentos em pilhas pela primeira letra e, em seguida, classifique cada pilha.

A pesquisa de palavras no dicionário geralmente é realizada por uma técnica semelhante à pesquisa binária, que é recursiva.

Nas organizações, os chefes geralmente dão comandos aos chefes de departamento, que por sua vez dão comandos aos gerentes e assim por diante.

Requisito do mundo real que recebi recentemente:

Requisito A: implemente este recurso após entender completamente o Requisito A.

Analisadores e compiladores podem ser escritos em um método descendente recursivo. Não é a melhor maneira de fazer isso, já que ferramentas como lex / yacc geram analisadores mais rápidos e eficientes, mas conceitualmente simples e fáceis de implementar, portanto, permanecem comuns.

A recursão é aplicada a problemas (situações) em que você pode dividi-la (reduzi-la) em partes menores, e cada parte (s) se parece com o problema original.

Bons exemplos de onde estão as coisas que contêm partes menores semelhantes a si mesmas:

• estrutura de árvore (um galho é como uma árvore)
• listas (parte de uma lista ainda é uma lista)
• recipientes (bonecas russas)
• sequências (parte de uma sequência se parece com a próxima)
• grupos de objetos (um subgrupo ainda é um grupo de objetos)

A recursão é uma técnica para quebrar continuamente o problema em pedaços cada vez menores, até que um desses pedaços se torne pequeno o suficiente para ser um pedaço de bolo. É claro que, depois de separá-los, você terá que "costurar" os resultados na ordem certa para formar uma solução total para o problema original.

Alguns algoritmos de classificação recursiva, algoritmos de caminhada em árvore, algoritmos de mapeamento / redução, divisão e conquista são todos exemplos dessa técnica.

Em programação de computador, a maioria das linguagens de tipo de retorno de chamada baseadas em pilha já têm os recursos integrados para recursão: ou seja,

• dividir o problema em partes menores ==> chamar a si mesmo em um subconjunto menor dos dados originais),
• acompanhe como as peças são divididas ==> pilha de chamadas,
• costurar os resultados de volta ==> retorno baseado em pilha

Eu tenho um sistema que usa recursão de cauda pura em alguns lugares para simular uma máquina de estado.

Alguns ótimos exemplos de recursão são encontrados em linguagens de programação funcionais . Em linguagens de programação funcional ( Erlang , Haskell , ML / OCaml / F # , etc.), é muito comum que qualquer processamento de lista use recursão.

Ao lidar com listas em linguagens de estilo OOP imperativas típicas, é muito comum ver listas implementadas como listas vinculadas ([item1 -> item2 -> item3 -> item4]). No entanto, em algumas linguagens de programação funcional, você descobre que as próprias listas são implementadas recursivamente, onde a "cabeça" da lista aponta para o primeiro item da lista e a "cauda" aponta para uma lista contendo o resto dos itens ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]]). É muito criativo na minha opinião.

Essa manipulação de listas, quando combinada com correspondência de padrões, é MUITO poderosa. Digamos que eu queira somar uma lista de números:

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

Isso basicamente diz "se formos chamados com uma lista vazia, retorne 0" (permitindo-nos quebrar a recursão), caso contrário, retorne o valor de head + o valor de Sum chamado com os itens restantes (portanto, nossa recursão).

Por exemplo, posso ter uma lista de URLs , acho que separo todos os URLs aos quais cada URL se vincula e, em seguida, reduzo o número total de links de / para todos os URLs para gerar "valores" para uma página (uma abordagem que o Google leva com o PageRank e que você pode encontrar definido no papel MapReduce original ). Você também pode fazer isso para gerar contagens de palavras em um documento. E muitas, muitas outras coisas também.

Você pode estender esse padrão funcional para qualquer tipo de código MapReduce onde você pode pegar uma lista de algo, transformá-lo e retornar algo mais (seja outra lista ou algum comando zip na lista).

XML, ou percorrer qualquer coisa que seja uma árvore. Embora, para ser honesto, eu quase nunca use a recursão no meu trabalho.

Loops de feedback em uma organização hierárquica.

O chefe principal diz aos executivos para coletar feedback de todos na empresa.

Cada executivo reúne seus subordinados diretos e lhes diz para coletar feedback de seus subordinados diretos.

E assim por diante.

Pessoas sem subordinados diretos - os nós folha da árvore - dão seu feedback.

O feedback sobe na árvore com cada gerente adicionando seu próprio feedback.

Eventualmente, todo o feedback volta para o chefe.

Esta é a solução natural porque o método recursivo permite a filtragem em cada nível - a comparação de duplicatas e a remoção de feedback ofensivo. O chefe poderia enviar um e-mail global e fazer com que cada funcionário reportasse feedback diretamente para ele / ela, mas existem os problemas "você não consegue lidar com a verdade" e "você está demitido", então a recursão funciona melhor aqui.

Suponha que você esteja construindo um CMS para um site, onde suas páginas estão em uma estrutura de árvore, com, digamos, a raiz sendo a página inicial.

Suponha também que seu {usuário | cliente | cliente | chefe} solicite que você coloque uma trilha de navegação em cada página para mostrar onde você está na árvore.

Para qualquer página n fornecida, você pode querer ir até o pai de n, e seu pai, e assim por diante, recursivamente para construir uma lista de nós de volta à raiz da árvore da página.

Claro, você está acessando o banco de dados várias vezes por página nesse exemplo, então você pode querer usar algum aliasing SQL onde você procura a tabela de páginas como a, e tabela de páginas novamente como b, e une a.id com b.parent para que você faça o banco de dados fazer as junções recursivas. Já faz um tempo, então minha sintaxe provavelmente não ajuda.

Então, novamente, você pode querer apenas calcular isso uma vez e armazená-lo com o registro da página, atualizando-o apenas se você mover a página. Isso provavelmente seria mais eficiente.

Enfim, esse é meu $ 0,02

Você tem uma árvore de organização com N níveis de profundidade. Vários dos nós são verificados e você deseja expandir apenas para os nós que foram verificados.

Isso é algo que eu realmente codifiquei. É bom e fácil com recursão.

No meu trabalho, temos um sistema com uma estrutura de dados genérica que pode ser descrita como uma árvore. Isso significa que a recursão é uma técnica muito eficaz para trabalhar com os dados.

Resolvê-lo sem recursão exigiria muito código desnecessário. O problema da recursão é que não é fácil acompanhar o que acontece. Você realmente precisa se concentrar ao seguir o fluxo de execução. Mas quando funciona, o código é elegante e eficaz.

Cálculos para finanças / física, como médias compostas.

• Analisando um arquivo XML .
• Pesquisa eficiente em espaços multidimensionais. Por exemplo. quad-trees em 2D, oct-trees em 3D, kd-trees, etc.
• Agrupamento hierárquico.
• Venha para pensar sobre isso, atravessar qualquer estrutura hierárquica naturalmente se presta à recursão.
• Metaprogramação de template em C ++, onde não há loops e a recursão é a única maneira.

Analisando uma árvore de controles em Windows Forms ou WebForms (.NET Windows Forms / ASP.NET ).

O melhor exemplo que conheço é quicksort , é muito mais simples com recursão. Dê uma olhada em:

shop.oreilly.com/product/9780596510046.do

www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(Clique no primeiro subtítulo do capítulo 3: "O código mais bonito que já escrevi").

As empresas de telefonia e cabo mantêm um modelo de sua topologia de fiação, que na verdade é uma grande rede ou gráfico. A recursão é uma maneira de percorrer este modelo quando você deseja localizar todos os elementos pais ou filhos.

Uma vez que a recursão é cara do ponto de vista do processamento e da memória, esta etapa normalmente só é executada quando a topologia é alterada e o resultado é armazenado em um formato de lista pré-ordenado modificado.

O raciocínio indutivo, o processo de formação de conceitos, é recursivo por natureza. Seu cérebro faz isso o tempo todo, no mundo real.

Idem ao comentário sobre compiladores. Os nós da árvore de sintaxe abstrata naturalmente se prestam à recursão. Todas as estruturas de dados recursivas (listas vinculadas, árvores, gráficos, etc.) também são mais facilmente tratadas com recursão. Acho que a maioria de nós não consegue usar muito a recursão depois que saímos da escola por causa dos tipos de problemas do mundo real, mas é bom estar ciente disso como uma opção.

A multiplicação de números naturais é um exemplo do mundo real de recursão:

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x