Recursão
Tags: computerscience
Published: 2021-05-02 16:57:05

>"Você só entende recursão se você entende recursão"
>Homer Simpson

Matematicamente, quando usamos recursão, estamos na verdade usando o Princípio da Indução Finita (PIF). O PIF é muito utilizado para resolver problemas discretos, que envolvem números naturais. 
Por exemplo, dada a progressão aritmética,

<a href="https://www.codecogs.com/eqnedit.php?latex=S(n)&space;=&space;1&plus;&space;2&space;&plus;&space;\dots&space;&plus;n" target="_blank"><img src="https://latex.codecogs.com/gif.latex?S(n)&space;=&space;1&plus;&space;2&space;&plus;&space;\dots&space;&plus;n" title="S(n) = 1+ 2 + \dots +n" /></a>

Queremos mostrar que  
<a href="https://www.codecogs.com/eqnedit.php?latex=S(n)&space;=&space;\frac{n(n&plus;1)}{2}" target="_blank"><img src="https://latex.codecogs.com/gif.latex?S(n)&space;=&space;\frac{n(n&plus;1)}{2}" title="S(n) = \frac{n(n+1)}{2}" /></a>
Nesse exemplo, assumimos que a fórmula é válida para o caso trivial, o que é simples de demonstrar:
<a href="https://www.codecogs.com/eqnedit.php?latex=S(1)&space;=&space;1&space;=&space;\frac{1(1&plus;1)}{2}" target="_blank"><img src="https://latex.codecogs.com/gif.latex?S(1)&space;=&space;1&space;=&space;\frac{1(1&plus;1)}{2}" title="S(1) = 1 = \frac{1(1+1)}{2}" /></a>

O próximo passo é considerar que sabendo resolver o problema para n-1 elementos, eu consigo também resolver para n:
<a href="https://www.codecogs.com/eqnedit.php?latex=S(n)=S(n-1)&space;&plus;&space;n&space;=&space;\dots&space;=&space;\frac{n(n&plus;1)}{2}" target="_blank"><img src="https://latex.codecogs.com/gif.latex?S(n)=S(n-1)&space;&plus;&space;n&space;=&space;\dots&space;=&space;\frac{n(n&plus;1)}{2}" title="S(n)=S(n-1) + n = \dots = \frac{n(n+1)}{2}" /></a>
A ideia da recursão, no sentido de resolver problemas computacionais, é dividir um problema original em subproblemas menores da mesma natureza (divisão) e depois combinar as soluções obtidas para gerar a solução do problema maior (conquista). No fundo, ao demonstrar qualquer teorema usando PIF, estamos aplicando essa mesma ideia.
Uma primeira implementação ingênua de um algoritmo recursivo de busca pode ser 
```cpp
int busca (int[] A, int valor, int n) {
if (n == 1) {
if (A[0] == valor)
    return 0;
else 
   return 1;
}
else {
if (A[n-1] == valor)
    return n-1;
else 
   return busca(A, valor, n-1);
   }
}
```
**Caso base**: o arranjo é unitário e o elemento é igual ou diferente do valor buscado
**Hipótese indutiva**:
Nessa implementação, primeiramente avaliamos se o vetor é unitário, e nesse caso, já retornamos o primeiro elemento caso seja encontrado, ou retornamos que ele não foi encontrado. 
Caso contrário, eu avalio se a posição n-1 me fornece o valor procurado, e caso contrário, eu faço novamente uma busca binária para n-1 elementos, avaliando agora se n-2 (que agora é o penúltimo elemento) satisfaz a minha condição de busca, dividindo sucessivamente o problema até que a solução seja encontrada, retornando 0, ou eu termine com um vetor unitário que não seja o valor esperado, retornando assim 1.
É como se tivéssemos usando um dominó para em seguida derrubar toda a sequência dos mesmos.

Existe uma categoria sofisticada de algoritmos recursivos de busca, os chamados algoritmos de divisão e conquista, que costumam ser algoritmos muito eficientes e utilizam a  o teorema de indução finita forte. Dessa vez, admitimos como hipótese de indução que já sabemos ordenar uma metade do problema dado, para a seguir provar que conseguimos ordenar a segunda metade.
As demonstração do Princípio da Indução Finita em suas várias formas equivalentes, pode ser encontrada em bons [livros de análise](https://impa.br/page-livros/analise-real-vol-1-funcoes-de-uma-variavel/) ou em livros de [algoritmos](https://www.amazon.com.br/Algoritmos-Teoria-Pr%C3%A1tica-Thomas-Cormen/dp/8535236996). 
Assim, cada instância do problema é dividida em duas ou mais instâncias menores;
Cada instância menor é resolvida usando o próprio algoritmo que está sendo definido;
Um exemplo muito legal de algoritmo que utiliza essa estratégia é o algoritmo de [busca binária](https://en.wikipedia.org/wiki/Binary_search_algorithm).

E... é isso. Eu só gostaria de poder falar um pouco sobre essa extraordinária conexão que existe entre matemática e computação e que muitas vezes não fica muito evidente no dia-a-dia :-)