Quando usar recursão?

Quando são algumas instâncias (relativamente) básicas (pense no primeiro ano do ensino médio) quando alguém usaria recursão em vez de apenas um loop?

Eu ensinei C ++ para estudantes de graduação por cerca de dois anos e cobri recursão. Pela minha experiência, sua pergunta e sentimentos são muito comuns. No extremo, alguns alunos veem a recursão como difícil de entender, enquanto outros querem usá-la para praticamente tudo.

Acho que Dave resume bem: use-o onde for apropriado. Ou seja, use-o quando parecer natural. Quando você enfrentar um problema em que ele se encaixa perfeitamente, você provavelmente o reconhecerá: parece que você nem consegue encontrar uma solução iterativa. Além disso, a clareza é um aspecto importante da programação. Outras pessoas (e você também!) Devem poder ler e entender o código que você produz. Eu acho que é seguro dizer que loops iterativos são mais fáceis de entender à primeira vista do que recursão.

Eu não sei o quão bem você conhece programação ou ciência da computação em geral, mas sinto fortemente que não faz sentido falar sobre funções virtuais, herança ou sobre qualquer conceito avançado aqui. Eu frequentemente comecei com o exemplo clássico de computação de números de Fibonacci. Cabe aqui, pois os números de Fibonacci são definidos recursivamente . É fácil de entender e não requer nenhum recurso sofisticado do idioma. Depois que os alunos obtiveram algum entendimento básico de recursão, examinamos novamente algumas funções simples que criamos anteriormente. Aqui está um exemplo:

Uma string contém um caractere ?$x$

Foi assim que fizemos antes: itere a string e veja se algum índice contém .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

A questão é, então, pode nós fazemos isso de forma recursiva? Claro que podemos, aqui está uma maneira:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

A próxima questão natural é: devemos fazer assim? Provavelmente não. Por quê? É mais difícil de entender e mais difícil de inventar. Portanto, é mais propenso a erros também.

As soluções para alguns problemas são mais naturalmente expressas usando recursão.

Por exemplo, suponha que você tenha uma estrutura de dados em árvore com dois tipos de nós: folhas, que armazenam um valor inteiro; e ramificações, que possuem uma subárvore esquerda e direita em seus campos. Suponha que as folhas estejam ordenadas, de modo que o valor mais baixo esteja na folha mais à esquerda.

Suponha que a tarefa seja imprimir os valores da árvore em ordem. Um algoritmo recursivo para fazer isso é bastante natural:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Escrever código equivalente sem recursão seria muito mais difícil. Tente!

De maneira mais geral, a recursão funciona bem para algoritmos em estruturas de dados recursivas, como árvores, ou para problemas que podem naturalmente ser divididos em subproblemas. Confira, por exemplo, dividir e conquistar algoritmos .

Se você realmente deseja ver recursão em seu ambiente mais natural, deve procurar uma linguagem de programação funcional como Haskell. Nessa linguagem, não há construto em loop, então tudo é expresso usando recursão (ou funções de ordem superior, mas essa é outra história, que vale a pena conhecer também).

Observe também que linguagens de programação funcionais executam recursão de cauda otimizada. Isso significa que eles não estabelecem um quadro de pilha, a menos que não precisem --- essencialmente, a recursão pode ser convertida em um loop. De uma perspectiva prática, você pode escrever código de maneira natural, mas obter o desempenho do código iterativo. Para o registro, parece que os compiladores C ++ também otimizam chamadas de cauda , portanto, não há sobrecarga adicional no uso de recursão em C ++.

De alguém que praticamente vive em recursão , tentarei lançar alguma luz sobre o assunto.

Quando introduzida pela primeira vez na recursão, você aprende que é uma função que se autodenomina e é basicamente demonstrada com algoritmos como o percurso da árvore. Mais tarde, você descobrirá que é muito usado em programação funcional para linguagens como LISP e F #. Com o F # que escrevo, a maior parte do que escrevo é de correspondência recursiva e de padrões.

Se você aprender mais sobre programação funcional como o F #, aprenderá que as listas do F # são implementadas como listas vinculadas individualmente, o que significa que as operações que acessam apenas o cabeçalho da lista são O (1) e o acesso ao elemento é O (n). Depois de aprender isso, você tende a percorrer os dados como lista, construindo uma nova lista na ordem inversa e depois revertendo a lista antes de retornar da função, que é muito eficaz.

Agora, se você começar a pensar sobre isso, logo perceberá que funções recursivas enviarão um quadro de pilha toda vez que uma chamada de função for feita e podem causar um estouro de pilha. No entanto, se você construir sua função recursiva para que ela possa executar uma chamada final e o compilador oferecer suporte à capacidade de otimizar o código da chamada final. ou seja, campo .NET OpCodes.Tailcall, você não causará um estouro de pilha. Nesse ponto, você começa a escrever qualquer loop como uma função recursiva e qualquer decisão como uma correspondência; os dias ife whileagora são história.

Depois de migrar para a IA usando o retorno em idiomas como PROLOG, tudo é recursivo. Embora isso exija pensar de uma maneira bem diferente do código imperativo, se o PROLOG for a ferramenta certa para o problema, ele libera o ônus de ter que escrever muitas linhas de código e pode reduzir drasticamente o número de erros. Veja: Cliente Amzi e oTek

Para voltar à sua pergunta sobre quando usar a recursão; Uma maneira de encarar a programação é com hardware em uma extremidade e conceitos abstratos na outra. Quanto mais próximo do hardware o problema, mais penso em linguagens imperativas ife while, quanto mais abstrato o problema, mais penso em linguagens de alto nível com recursão. No entanto, se você começar a escrever código de sistema de baixo nível e assim por diante, e quiser verificar se é válido, encontrará soluções como provadores de teoremas que são úteis, que dependem muito da recursão.

Se você olhar para Jane Street , verá que eles usam a linguagem funcional OCaml . Embora eu não tenha visto nenhum código, ao ler sobre o que eles mencionam, eles estão pensando recursivamente.

EDITAR

Como você está procurando uma lista de usos, darei uma idéia básica do que procurar no código e uma lista de usos básicos que são baseados principalmente no conceito de catamorfismo que está além do básico.

Para C ++: Se você definir uma estrutura ou uma classe que possui um ponteiro para a mesma estrutura ou classe, a recursão deve ser considerada para os métodos transversais que usam os ponteiros.

O caso simples é uma lista vinculada unidirecional. Você processaria a lista iniciando na cabeça ou na cauda e, em seguida, percorresse recursivamente a lista usando os ponteiros.

Uma árvore é outro caso em que a recursão é frequentemente usada; tanto que, se você vê a travessia de árvores sem recursão, deve começar a perguntar por quê? Não está errado, mas algo que deve ser observado nos comentários.

Os usos comuns da recursão são:

• triagem
• procurando
• mapa
• dobra
• filtro

Para fornecer um caso de uso menos arcano do que os dados nas outras respostas: a recursão combina muito bem com estruturas de classes semelhantes a árvores (Orientadas a Objetos) derivadas de uma fonte comum. Um exemplo de C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

O exemplo acima usa recursão: ComputeValue é implementado recursivamente. Para fazer o exemplo funcionar, use funções virtuais e herança. Você não sabe exatamente o que são as partes esquerda e direita da classe Plus, mas não se importa: é algo que pode calcular seu próprio valor, que é tudo o que você precisa saber.

A vantagem crucial da abordagem acima é que toda classe cuida de seus próprios cálculos . Você separa completamente as diferentes implementações de todas as subexpressões possíveis: elas não têm conhecimento do funcionamento uma da outra. Isso facilita o raciocínio sobre o programa e, portanto, facilita a compreensão, manutenção e extensão do programa.

O primeiro exemplo usado para ensinar recursão na minha aula de programação inicial foi uma função para listar todos os dígitos em um número separadamente na ordem inversa.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Ou algo assim (estou saindo da memória aqui e não testando). Além disso, quando você entrar em classes de nível superior, usará muito a recursão, especialmente em algoritmos de pesquisa, algoritmos de classificação etc.

Portanto, pode parecer uma função inútil no idioma agora, mas é muito, muito útil a longo prazo.