Relações de recorrência
Relações de recorrência são equações que definem uma sequência recursiva, ou seja, cada termo da sequência é calculado a partir dos anteriores. Um exemplo simples é:
$$ \begin{align}
a_n &= a_{n - 1} + 5 \\
a_0 &= 0 \\
\end{align} $$
Que define todos os múltiplos não-negativos de 5: {0, 5, 10, 15, 20, ...}. Embora relações de recorrência sejam relativamente simples de se traduzir em algoritmo, o mais eficiente seria se pudéssemos encontrar fórmulas fechadas, que não dependem dos termos anteriores. Neste caso mostrado, a fórmula é bastante fácil de encontrar: \(a_n = 5n\). Mas geralmente não é tão óbvio e simples assim, infelizmente.
Recursividade
Em programação, recursividade ou recursão é uma técnica que consiste em solucionar um problema quebrando-o em partes menores que podem ser resolvidas separadamente para compor a solução geral. Assim, reduzimos a complexidade até os componentes mais triviais, que sabemos como resolver.
Suponha, por exemplo, que queremos descobrir o n-ésimo termo da sequência descrita acima (admitindo que não conhecemos a fórmula fechada). Ora, a própria definição da sequência nos dá o caso base ou solução trivial: n = 0, para o qual \(a_0 = 0\). Se n for diferente de zero, calculamos n - 1 e somamos 5. Se n - 1 for diferente de zero, calculamos n - 2 e somamos 5... e assim por diante, até n = 0.
int termo(int n) {
if(n == 0)
return 0;
else
return (termo(n - 1) + 5);
}
Como exercício, elabore um algoritmo recursivo que calcule o resto da divisão inteira entre os números naturais a e b, a partir da operação de subtração.
Agora veremos alguns exemplos de sequências recursivas muito importantes que aparecem em diversos problemas de competições.
A sequência de Fibonacci
Definida pela relação de recorrência \(F_n = F_{n - 1} + F_{n - 2}\), tal que \(F_0 = 0, F_1 = 1\).
Fibonacci explorou a sequência ao propor um problema interessante envolvendo uma população de coelhos: a população inicial é de um par de coelhos recém-nascidos, um macho e uma fêmea; cada par gera um novo par de um macho e uma fêmea a cada mês e uma fêmea pode se reproduzir a partir de um mês de vida. Considerando que nenhum coelho morra, quantos pares haverá após 1 ano?
- Após 1 mês, ainda haverá 1 par.
- Passados 2 meses, a fêmea gera um novo par, totalizando 2 pares.
- Passados 3 meses, a fêmea original gera um novo par, totalizando 3 pares.
- Passados 4 meses, as duas primeiras fêmeas geram dois novos pares, totalizando 5 pares.
- ...
- Passados 12 meses, haverá 233 pares.
Que correspondem justamente aos números na sequência de Fibonacci. A fórmula fechada é dada por:
$$ F_n = \frac{1}{\sqrt{5}} \left ( \left (\frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right ) $$
... Não muito intuitivo, certo?
Números de Catalan
Esta sequência está associada a inúmeros problemas em combinatória, mas vamos nos focar em um deles: dados n pares de parênteses, quantas sequências válidas podemos construir? Por exemplo, com 2 pares, podemos fazer: ()() e (()). Com 3 pares: ()()(), ()(()), (())() e ((())). Isso corresponde a calcular o n-ésimo número de Catalan, \(C_n\).
O parêntese inicial, l, deve ser combinado com algum parêntese de fechamento r. Note que isso divide a sequência em duas partes: entre l e r, com k pares de parênteses, e depois de r, com n - k - 1 pares (lembrando que l e r já formam um par). Todos esses pares devem formar sequências válidas. Além disso, k pode assumir qualquer valor de 0 até n - 1. Daí:
$$ C_{n} = \sum_{k = 0}^{n - 1} = C_{k}C_{n - k - 1} $$
E \(C_0 = 1\), pois só há uma sequência, vazia, contendo zero pares de parênteses. A fórmula fechada admite inúmeras demonstrações: \(C_n = \frac{1}{n+1} \binom{2n}{n}\).
Números de Stirling
Há dois tipos de números de Stirling: de primeira ordem e segunda ordem. Aqui vamos tratar da sequência composta pelos números de Stirling de segunda ordem, que contam os modos de particionar n itens em k conjuntos, \(\left \{ ^{n}_{k} \right \}\). Isso equivale a descobrir a quantidade de distribuições de n objetos distintos em k caixas idênticas, problema explorado aqui.
Ao inserir o n-ésimo item, há duas possibilidades: ou esse item forma um conjunto com um único elemento ou ele entra em um dos k conjuntos existentes. No primeiro caso, há \(\left \{ ^{n - 1}_{k - 1} \right \}\) modos de distribuir os n - 1 itens restantes. No segundo caso, o item pode entrar em qualquer um dos k conjuntos que particionam n - 1 itens em k conjuntos. Portanto:
$$ \left \{ ^{n}_{k} \right \} = \left \{ ^{n - 1}_{k - 1} \right \} + k \left \{^{n - 1}_{k} \right \} $$
Se n > 0, \(\left \{ ^{n}_{n} \right \} = 1\). Se n >= 0, \(\left \{ ^{n}_{0} \right \} = 0\).
Partições de inteiros em parcelas
Particionar um inteiro significa dividi-lo em parcelas tal que a soma dessas parcelas resulte no número original. As partições de 6 com 2 parcelas são as seguintes:
6 = 5 + 1
6 = 4 + 2
6 = 3 + 3
Então, part(6, 2) = 3. Como vimos neste post sobre distribuições de objetos em caixas, part(n, k) equivale ao número de partições de n em k parcelas e o número de distribuições de n objetos idênticos em k caixas idênticas. Para determinar uma fórmula recursiva, começamos dividindo as partições em 2 grupos para depois somarmos:
- Grupo A: Partições com pelo menos um termo "1" (como em 6 = 5 + 1 e 5 = 1 + 1 + 4).
- Grupo B: Partições sem nenhum termo "1" (como em 6 = 4 + 2).
- Grupo A
Quanto ao grupo A, basicamente estamos interessados no número de formas que podemos utilizar o número 1 para formar o número desejado. Vamos ao exemplo das partições nesse grupo em part(5, 3), que possuem a seguinte forma genérica:
5 = 1 + x + y
Como podemos simplificar isso? Bem, sabemos que o 1 está em todas as partições do grupo, então o que acontece quando o "cortamos" dos dois lados?
5 - 1 = 1 + x + y - 1
4 = x + y
Olha que interessante, agora o problema foi reduzido a encontrar part(4, 2), já que o termo 1 foi removido. De fato, esse raciocínio pode ser aplicado a qualquer partição do grupo A em qualquer situação, o que nos leva a part(n - 1, k - 1) como sendo o total de partições pertencentes ao nosso primeiro grupo.
- Grupo B
Sabemos que todos os termos presentes nas partições do grupo B são maiores que 1, então podemos subtrair 1 de cada um deles e deixar inteiros positivos como resultado. O que acontece quando fazemos isso? Vamos testar com uma partição de part(8, 3):
8 = 2 + 2 + 4
Temos 3 termos, então subtraímos 3 vezes:
8 - 1 - 1 - 1 = 1 + 1 + 3
5 = 1 + 1 + 3
Isso é promissor. Que tal mais uma?
8 = 2 + 3 + 3
8 - 1 - 1 - 1 = 1 + 2 + 2
5 = 1 + 2 + 2
Consegue ver o que acontece? Cada uma das partições do grupo B é equivalente a uma partição de part(5, 3). E de onde vem esse 5? Simples, é porque temos que subtrair 1 de 8 para cada termo, ou seja, equivale a 8 - 3. É desse modo que reduzimos o problema de "encontrar as partições pertencentes ao grupo B de part(8, 3)" a "encontrar part(5, 3)".
Portanto, chegamos à conclusão de que o número de partições do grupo B é part(n - k, k).
- Fórmula geral
Some os dois grupos e você terá sua formulinha mágica:
part(n, k) = part(n - 1, k - 1) + part(n - k, k)
As soluções triviais são k = 1, para o qual part(n, k) = 1, e n = 0 ou n = 1, para os quais part(n, k) = 1.
Fontes
Catalan number - Wikipedia
Fibonacci number - Wikipedia
Partition Recurrence Relation
Programming Challenges, de Steven Skiena e Miguel Revilla (mais informações sobre o livro)
Recursão e algoritmos recursivos
Postagens
0 comentários:
Postar um comentário