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

As estruturas de diretório / arquivo são o melhor exemplo de uso para recursão, porque todos as compreendem antes de começar, 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;
}

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 antes do que com estruturas de dados lineares, como listas.

Coisas para pensar:

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

Tudo isso está relacionado a cenários reais do mundo real, e todos podem ser usados em aplicações de importância no mundo real.

link

• modelando uma infecção contagiosa
• gerando geometria
• gerenciamento de diretório
• ordenação

link

• raytracing
• xadrez
• analisando o código-fonte (gramática de idiomas)

link

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

link

• Dá uma boa história em inglês que ilustra a recursão de uma história para dormir.

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

• Mesclar ordem
• Pesquisa binária
• Traversal, Insertion and Removal em árvores (amplamente usado em aplicativos de banco de dados)
• Gerador de permutações
• Solucionador de Sudoku (com backtracking)
• Verificação ortográfica (novamente com retrocesso)
• Análise de sintaxe (por exemplo, um programa que converte prefixo para notação postfix)

O QuickSort seria o primeiro a ser lembrado. A pesquisa binária também é um problema recursivo. Além disso, há classes inteiras de problemas que as soluções são quase gratuitas quando você começa a trabalhar com recursão.

Classifique, 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:] )

Alguns exemplos que não envolvem matemática para ensinar recursão (pelo menos, os problemas dos quais me lembro nos meus anos de universidade):

Torres de Hanói
• Oito rainhas

Estes são exemplos do uso do Backtracking para resolver o problema.

Outros problemas são clássicos do domínio Inteligência Artificial: Usando Profundidade Primeira pesquisa, pathfinding, planejamento.

Todos esses problemas envolvem algum tipo de estrutura de dados "complexa", mas se você não quiser ensiná-la com matemática (números), suas escolhas podem ser mais limitadas. Yoy 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 forma: Vazio + N = N Nó (X) + N = Nó (X + N)

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

Existem muitas soluções na web em muitos idiomas diferentes.

Um detector de palíndromo:

Comece com uma string: "ABCDEEDCBA" Se iniciar & caracteres finais são iguais, então recurse e verifique "BCDEEDCB", etc ...

Um algoritmo de busca binária parece com o que você quer.

Em linguagens de programação funcionais, quando nenhuma função de ordem superior está disponível, a recursão é usada em vez de loops imperativos para evitar o estado mutável.

F # é uma linguagem funcional impura que permite ambos os estilos, então vou comparar ambos aqui. A soma a seguir 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

Observe que esse tipo de agregação é capturada na função de ordem superior List.fold e poderia ser escrita como List.fold (+) 0 xlist ou, na verdade, ainda mais simplesmente com a função de conveniência List.sum como apenas List.sum xlist .

Eu usei muito a recursão no jogo jogando AI. Escrevendo em C ++, fiz uso de uma série de cerca de 7 funções que chamam umas às outras em ordem (com a primeira função tendo uma opção para 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 queria procurar fosse para 0, caso em que a função final chamaria minha função de avaliação e retornaria a pontuação da posição.

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

Você pode ver um resumo básico desse tipo de programa, consulte o link

Um bom exemplo da vida real nos negócios é algo chamado "Lista de Materiais". Estes 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ões, rodas, quadro, etc. E cada um desses componentes pode ter subcomponentes. por exemplo, a Roda pode ter Raios, uma haste de válvula, etc. Normalmente, eles são representados em uma estrutura de árvore.

Agora, para consultar qualquer informação agregada sobre a lista de materiais 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 mais campos. Você pode precisar descobrir quantos componentes de plástico 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.

As relações familiares são bons exemplos porque todos as compreendem intuitivamente:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);

Uma operação interna bastante recursiva, embora inútil, é recursiva. 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.

Outro problema de recursão do mundo real com o qual os alunos podem se relacionar é construir 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.).

Eu resolvi um problema com um padrão de cavaleiro (em um tabuleiro de xadrez) usando um programa recursivo. Você deveria mover o cavalo para que ele tocasse em 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 "pensar em frente" podem ser trabalhados testando futuras possibilidades em uma árvore como essa.