Recursão sem fatorial, números de Fibonacci, etc.

48

Quase todos os artigos que posso encontrar sobre recursão incluem exemplos de números fatoriais ou de Fibonacci, que são:

  1. Matemática
  2. Inútil na vida real

Existem alguns exemplos de códigos não matemáticos interessantes para ensinar recursão?

Estou pensando em algoritmos de dividir e conquistar, mas eles geralmente envolvem estruturas de dados complexas.

preguiçoso
fonte
26
Embora sua pergunta seja completamente válida, eu hesitaria em chamar os números de Fibonacci de inúteis na vida real . O mesmo vale para fatorial .
Zach L
2
The Little Schemer é um livro inteiro sobre recursão que nunca usa Fato ou Fib. junix-linux-config.googlecode.com/files/…
Eric Wilson
5
@Zach: Mesmo assim, a recursão é uma maneira horrível de implementar os números de Fibonacci, devido ao tempo de execução exponencial.
Dan04 13/09/11
2
@ dan04: A recursão é uma maneira horrível de implementar quase tudo devido à possibilidade de estouro de pilha na maioria das linguagens.
R ..
5
@ dan04 a menos que sua linguagem é bastante inteligente para implementar a otimização de cauda chamada como a maioria das linguagens funcionais, caso em que ele funciona muito bem
Zachary K

Respostas:

107

As estruturas de diretório / arquivo são o melhor exemplo de uso para recursão, porque todo mundo as entende antes de iniciar, mas qualquer coisa que envolva estruturas semelhantes a árvores serve.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}
pdr
fonte
1
Obrigado, acho que vou com o sistema de arquivos. É algo concreto e pode ser usado para muitos exemplos do mundo real.
synapse
9
Nota: o comando unix geralmente exclui a opção -r (cp ou rm, por exemplo). -r significa recursivo.
Deadalnix 13/09/11
7
você precisa ter um pouco de cuidado aqui, pois no mundo real os sistemas de arquivos são na verdade um gráfico direcionado, não necessariamente uma árvore, se suportados pelo sistema de arquivos, links físicos etc. podem criar junções e ciclos
jk.
1
@jk: Os diretórios não podem ter links físicos, então modulo algumas folhas que podem aparecer em mais de um local e, assumindo que você exclui links simbólicos, os sistemas de arquivos do mundo real são árvores.
R ..
1
existem outras peculiaridades em alguns sistemas de arquivos para diretórios, por exemplo, pontos de nova análise NTFS. O que quero dizer é que o código que não está especificamente ciente disso pode ter resultados inesperados nos sistemas de arquivos do mundo real
jk.
51

Procure por coisas que envolvam estruturas de árvores. Uma árvore é relativamente fácil de entender, e a beleza de uma solução recursiva se torna aparente muito mais cedo do que com estruturas de dados lineares, como listas.

Coisas para pensar:

  • sistemas de arquivos - são basicamente árvores; uma boa tarefa de programação seria buscar todas as imagens .jpg em um determinado diretório e todos os seus subdiretórios
  • ancestral - dada uma árvore genealógica, encontre o número de gerações que você precisa percorrer para encontrar um ancestral comum; ou verifique se duas pessoas na árvore pertencem à mesma geração; ou verifique se duas pessoas na árvore podem se casar legalmente (depende da jurisdição :)
  • Documentos do tipo HTML - converte entre a representação serial (texto) de um documento e uma árvore DOM; executar operações em subconjuntos de um DOM (talvez até implemente um subconjunto de xpath?); ...

Todos eles estão relacionados aos cenários reais do mundo real e podem ser usados ​​em aplicativos com significado no mundo real.

tdammers
fonte
Obviamente, deve-se notar que sempre que você tem a liberdade de criar sua própria estrutura em árvore, é quase sempre melhor manter indicadores / referências ao pai / próximo irmão / etc. nos nós para que você possa iterar sobre a árvore sem recursão.
R ..
1
O que os ponteiros têm a ver com isso? Mesmo quando você tem dicas para o primeiro filho, o próximo irmão e o pai, ainda precisa percorrer a árvore de alguma maneira e, em alguns casos, a recursão é a maneira mais viável.
tdammers 14/09
41

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

  • modelando uma infecção contagiosa
  • geometria geradora
  • gerenciamento de diretório
  • Ordenação

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

  • raytracing
  • xadrez
  • analisando o código fonte (gramática do idioma)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

  • Pesquisa BST
  • Torres de Hanói
  • pesquisa palíndromo

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

  • Dá uma bela história em inglês que ilustra a recursão de uma história de ninar.
mskfisher
fonte
10
Embora isso possa teoricamente responder à pergunta, seria preferível incluir aqui as partes essenciais dessas perguntas e respostas e fornecer os links para referência. Se as perguntas forem removidas do SO, sua resposta será completamente inútil.
Adam Lear
@ Anna Bem, os usuários não podem excluir suas perguntas, então qual a probabilidade de isso acontecer?
vemv 13/09/11
4
@vemv Exclua votos, moderadores, regras sobre o que está mudando de tópico ... isso pode acontecer. De qualquer maneira, é preferível ter uma resposta mais completa aqui do que enviar um visitante para quatro páginas diferentes logo de cara.
Adam Lear
@ Anna: Seguindo essa linha de raciocínio, todas as perguntas encerradas como "duplicata exata" devem ter a resposta do original colado. Esta questão é uma duplicata exata (das perguntas sobre SO), por que deveria receber um tratamento diferente do exato duplicatas de perguntas sobre programadores?
SF.
1
@SF Se pudéssemos fechá-lo como duplicado, faríamos, mas duplicatas entre sites não são suportadas. Programadores é um site separado, portanto, idealmente, as respostas aqui usariam o SO como qualquer outra referência, e não o delegariam inteiramente. Não é diferente do que apenas dizer "sua resposta está neste livro" - tecnicamente verdadeira, mas não pode ser usada imediatamente sem consultar a referência.
Adam Lear
23

Aqui estão alguns problemas mais práticos que me vêm à mente:

  • Mesclar Classificação
  • Pesquisa binária
  • Transversal, Inserção e Remoção em Árvores (amplamente utilizado em aplicativos de banco de dados)
  • Gerador de permutações
  • Solver de Sudoku (com retorno)
  • Verificação ortográfica (novamente com retorno)
  • Análise de sintaxe (.eg, um programa que converte prefixo em notação postfix)
Daniel Scocco
fonte
11

O QuickSort seria o primeiro a se lembrar. A pesquisa binária também é um problema recursivo. Além disso, existem classes inteiras de problemas, cujas soluções caem quase de graça quando você começa a trabalhar com recursão.

Zachary K
fonte
3
A pesquisa binária é frequentemente formulada como um problema recursivo, mas é trivial (e geralmente preferível) implementar de maneira imperativa.
macio
Dependendo do idioma que você está usando o código, pode ou não ser explicitamente recursivo ou imperativo ou recursivo. Mas ainda é um algoritmo recursivo, pois você está dividindo o problema em partes cada vez menores para chegar à solução.
Zachary K
2
@ Zachary: Algoritmos que podem ser implementados com recursão de cauda (como pesquisa binária) estão em uma classe espacial fundamentalmente diferente daquela que requer recursão real (ou suas próprias estruturas de estado com requisitos de espaço igualmente caros). Não acho que seja benéfico para eles serem ensinados juntos como se fossem iguais.
R ..
8

Sort, definido recursivamente em Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Mesclar, definido recursivamente.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Pesquisa linear, definida recursivamente.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Pesquisa binária, definida recursivamente.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )
S.Lott
fonte
6

Em certo sentido, recursão é dividir e conquistar soluções, que está elevando o espaço do problema para um menor, para ajudar a encontrar a solução para um problema simples e, em seguida, geralmente reconstruindo o problema original para compor a resposta certa.

Alguns exemplos que não envolvem matemática para ensinar recursão (pelo menos aqueles problemas que eu lembro dos meus anos de universidade):

Estes são exemplos de como usar o Backtracking para resolver o problema.

Outros problemas são clássicos do domínio de Inteligência Artificial: Usando a Pesquisa em Profundidade Primeira, busca de caminhos, planejamento.

Todos esses problemas envolvem algum tipo de estrutura de dados "complexa", mas se você não deseja ensiná-lo com matemática (números), suas escolhas podem ser mais limitadas. Você pode querer começar a ensinar com uma estrutura de dados básica, como uma Lista vinculada. Por exemplo, representando os números naturais usando uma Lista:

0 = lista vazia 1 = lista com um nó. 2 = lista com 2 nós. ...

defina a soma de dois números em termos dessa estrutura de dados, da seguinte maneira: Vazio + N = N Nó (X) + N = Nó (X + N)

Gabriel
fonte
5

As torres de Hanói são boas para ajudar a aprender a recursão.

Existem muitas soluções para ele na web em vários idiomas diferentes.

Oded
fonte
3
Este é realmente, na minha opinião, outro exemplo ruim. Primeiro, não é realista; não é um problema que as pessoas realmente tenham. Segundo, existem soluções não recursivas fáceis. (Um é: numere os discos. Nunca mova um disco para um disco da mesma paridade e nunca desfaça a última jogada que você fez. Se você seguir essas duas regras, resolverá o quebra-cabeça com a solução ideal. Não é necessária recursão. )
Eric Lippert
5

Um detector Palindrome:

Comece com uma string: "ABCDEEDCBA" Se os caracteres iniciais e finais forem iguais, execute novamente e marque "BCDEEDCB", etc ...

NWS
fonte
6
Isso também é trivial para resolver sem recursão e, IMHO, melhor resolvido sem ele.
Blrfl
3
Concordou, mas o OP pediu especificamente exemplos de ensino com o uso mínimo de estruturas de dados.
NWS
5
Não é um bom exemplo de ensino se seus alunos puderem pensar imediatamente em uma solução não recursiva. Por que alguém prestaria atenção quando seu exemplo é "Aqui está algo trivial para fazer com um loop. Agora vou mostrar a você um caminho mais difícil sem motivo aparente".
Restabeleça Monica
5

Um algoritmo de pesquisa binária soa como o que você deseja.

Sardathrion
fonte
4

Nas linguagens de programação funcional, quando não há funções de ordem superior disponíveis, a recursão é usada em vez de loops imperativos para evitar o estado mutável.

F # é uma linguagem funcional impura que permite os dois estilos, por isso vou comparar os dois aqui. A seguir soma todos os números em uma lista.

Loop imperativo com variável mutável

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Loop recursivo sem estado mutável

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Note-se que este tipo de agregação é capturado na função de ordem superior List.folde poderia ser escrita como List.fold (+) 0 xlistou mesmo ainda mais simples com a função de conveniência List.sumcomo apenas List.sum xlist.

Stephen Swensen
fonte
você mereceria mais pontos do que apenas um de mim. F # sem recursão seria muito tedioso, isso é ainda mais verdadeiro para Haskell que não possui construções em loop SOMENTE recursão!
Schoetbi 13/09/11
3

Eu usei a recursão fortemente no jogo jogando AI. Escrevendo em C ++, fiz uso de uma série de cerca de 7 funções que se chamam em ordem (com a primeira função tendo a opção de ignorar todas elas e chamar uma cadeia de mais 2 funções). A função final em qualquer cadeia chamou a primeira função novamente até que a profundidade restante que eu desejasse pesquisar fosse 0, nesse caso a função final chamaria minha função de avaliação e retornaria a pontuação da posição.

As múltiplas funções permitiram-me ramificar facilmente com base nas decisões dos jogadores ou em eventos aleatórios no jogo. Eu usava passagem por referência sempre que podia, porque estava passando por estruturas de dados muito grandes, mas devido à forma como o jogo foi estruturado, era muito difícil ter um "desfazer" na minha pesquisa, então Eu usaria a passagem por valor em algumas funções para manter meus dados originais inalterados. Por isso, mudar para uma abordagem baseada em loop, em vez de uma abordagem recursiva, se mostrou muito difícil.

Você pode ver um esboço muito básico desse tipo de programa, consulte https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode

David Stone
fonte
3

Um bom exemplo da vida real nos negócios é algo chamado "Lista de materiais". Esses são os dados que representam todos os componentes que compõem um produto acabado. Por exemplo, vamos usar uma bicicleta. Uma bicicleta possui guidão, rodas, estrutura, etc. E cada um desses componentes pode ter subcomponentes. por exemplo, a roda pode ter raios, uma haste de válvula etc. Então, normalmente, estes são representados em uma estrutura de árvore.

Agora, para consultar qualquer informação agregada sobre a lista técnica ou para alterar elementos em uma lista técnica, muitas vezes você recorre à recursão.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

E uma amostra de chamada recursiva ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

Obviamente, a Classe BomPart teria muitos outros campos. Talvez você precise descobrir quantos componentes plásticos você tem, quanto trabalho é necessário para construir uma peça completa, etc. Tudo isso volta à utilidade da Recursão em uma estrutura de árvore.

deepee1
fonte
Uma lista de materiais pode ser um desastre direcionado, e não uma árvore; por exemplo, a mesma especificação de parafuso pode ser usada por mais de um componente.
Ian
-1

As relações familiares são bons exemplos, porque todo mundo as entende intuitivamente:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);
Caleb
fonte
em que idioma esse código está escrito?
törzsmókus
@ törzsmókus Nenhum idioma específico. A sintaxe está bem próxima de C, Obj-C, C ++, Java e muitas outras linguagens, mas se você deseja um código real, pode ser necessário substituir um operador apropriado, como ||o OR.
Caleb
-1

Um funcionamento interno bastante inútil, mas mostrando recursão, é recursivo strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

Sem matemática - uma função muito simples. É claro que você não o implementa recursivamente na vida real, mas é uma boa demonstração de recursão.

dente afiado
fonte
-2

Outro problema de recursão do mundo real com o qual os alunos podem se relacionar é criar seu próprio rastreador da Web, que extrai informações de um site e segue todos os links desse site (e todos os links desses links, etc.).

GregW
fonte
2
Geralmente, isso é melhor atendido por uma fila de processos, em oposição à recursão no sentido tradicional.
macio
-2

Resolvi um problema com um padrão de cavaleiro (em um tabuleiro de xadrez) usando um programa recursivo. Você deveria mover o cavaleiro para que ele tocasse todos os quadrados, exceto alguns quadrados marcados.

Você simplesmente:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Muitos tipos de cenários de "pensamento antecipado" podem ser trabalhados testando possibilidades futuras em uma árvore como esta.

Bill K
fonte