Quase todos os artigos que posso encontrar sobre recursão incluem exemplos de números fatoriais ou de Fibonacci, que são:
- Matemática
- 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.
Respostas:
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.
fonte
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:
Todos eles estão relacionados aos cenários reais do mundo real e podem ser usados em aplicativos com significado no mundo real.
fonte
https://stackoverflow.com/questions/105838/real-world-examples-of-recursion
https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion
https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence
https://stackoverflow.com/questions/126756/examples-of-recursive-functions
fonte
Aqui estão alguns problemas mais práticos que me vêm à mente:
fonte
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.
fonte
Sort, definido recursivamente em Python.
Mesclar, definido recursivamente.
Pesquisa linear, definida recursivamente.
Pesquisa binária, definida recursivamente.
fonte
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)
fonte
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.
fonte
Um detector Palindrome:
Comece com uma string: "ABCDEEDCBA" Se os caracteres iniciais e finais forem iguais, execute novamente e marque "BCDEEDCB", etc ...
fonte
Um algoritmo de pesquisa binária soa como o que você deseja.
fonte
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
Loop recursivo sem estado mutável
Note-se que este tipo de agregação é capturado na função de ordem superior
List.fold
e poderia ser escrita comoList.fold (+) 0 xlist
ou mesmo ainda mais simples com a função de conveniênciaList.sum
como apenasList.sum xlist
.fonte
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
fonte
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.
E uma amostra de chamada recursiva ...
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.
fonte
As relações familiares são bons exemplos, porque todo mundo as entende intuitivamente:
fonte
||
oOR
.Um funcionamento interno bastante inútil, mas mostrando recursão, é recursivo
strlen()
: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.
fonte
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.).
fonte
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:
Muitos tipos de cenários de "pensamento antecipado" podem ser trabalhados testando possibilidades futuras em uma árvore como esta.
fonte