Material didático para Introdução à Programação

Alterações: 2018/06/18: primeira versão

Nesta seção apresentamos as ideias de como resolver um problema de forma recursiva, em particular ilustrando isso para resolver o seguinte problema: como gerar todos os números binários com exatamente k bits (considerandos os "zeros à esquerda")?.

Para que o problema seja natualmente resolvido por um algoritmo recursivo é preciso que ele seja facilmente quebrável em sub-problemas menores (denominamos esta técnica de resolução por divisão e conquista) e que depois as soluções dos problemas menores possam ser utilizadas para resolver o problema original.

O problema da geração dos binãrios com até k dígitos apresenta esta característica.

1. (divisão) Podemos quebrá-lo da seguinte forma: resolver para k dígitos pode ser feito resolvendo primeiro para k-1 dígitos (nesse caso a quebra é "linear").
2. (conquista) Uma vez encontrada a solução (l1, ..., lk) para k-1 dígitos, a solução para k dígitos é simplesmente ("0"+l1, ..., "0"+lk, "1"+l1, ..., "1"+lk) (indicando por "+' o operador de concatenação).

A construção da solução recursiva para resolver o problema seria então aplicar a recorrência para cada um dos sub-problemas e depois usar os resoltados devolvidos para compor a solução global.

Desse modo, para tentar resolver um problema recursivamente, deve-se primeiro imaginar como quebrar o problema, então fazer um raciocínio de como reagrupar as soluções parciais para formar a solução global.

Para o problema considerado claramente a quebra poderia ser feita no número de dígitos. Se desejamos gerar os binários com k dígitos, supnhamos então que alguém resolveu o problema com k-1 dígitos. Bem, se a solução para k-1 dígitos é a lista (0...0, 0...1, ..., 1...0, 1...1), então a solução global seria duplicar a lista dada, sendo que para cada uma das cópias adicionamos o dígito "0" à frente e na outra o dígito "1", ou seja, a solução seria a lista seguinte

00...0, 00...1, ..., 01...0, 01...1
10...0, 10...1, ..., 11...0, 11...1

Claro que um caso trivial, seria quando k=1, pois nesse caso k-1=0 resultando em uma lista vazia. Portanto a solução global seria apenas os números "0" e "1" (eles concatenados com sequência vazia resultari neles próprios). E essa poderia ser a condição de terminação a recorrência: se k=0, devolver <vazio>.

Assim, vamos esquematizar o algoritmo refletindo precisamente essa ideia

gerar_binario (k) {
  se (k==0) devolver <vazio>
  senao {

    lista_indutiva = gerar_binario(k-1); // recursao: "alguem" resolve com k-1 bits (divida)

    devolva (0+lista_indutiva, 1+lista_indutiva); // conquiste!
    }
  }

Simule o algoritmo acima e veja que para k=4 ele consegue construir a os 15 valores abaixo, na ordem correta.

Decimal Binário | Decimal Binário
      0    0000 |       8    1000
      1    0001 |       9    1001
      2    0010 |      10    1010
      3    0011 |      11    1011
      4    0100 |      12    1100
      5    0101 |      13    1101
      6    0110 |      14    1110
      7    0111 |      15    1111

Note que se a linguagem utilizada não permite a devolução de lista, deve-se usar parâmetros, como esquematizado abaixo.

gerar_binario (k, vetorStr) { // vetorStr eh vetor de strings, cada uma com k digitos
  se (k==0) voltar;
  senao {

    gerar_binario(k-1, vetorStr); // recursao: resolver com k-1 - preencher vetorStr com todas as palavras com precisamente k-1 bits

    copiar(vetorStr, vetorStrAux); // copiar o conteudo de vetorStr para vetorStrAux (vetor local)
    acrescentarBit(0, vetorStr); // acrescentar o bit "0" a cada palavra em vetorStr
    acrescentarBit(1, vetorStrAux); // acrescentar o bit "1" a cada palavra em vetorStrAux
    anexar(vetorStr, vetorStrAux); // anexar ao final de vetorStr os elementos de vetorStrAux
    // ao chegar nesse ponto temos todas as palavras com precisamente k bits!
    }
  }

Leônidas de Oliveira Brandão
http://line.ime.usp.br