Recursão

"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,

Queremos mostrar que


Nesse exemplo, assumimos que a fórmula é válida para o caso trivial, o que é simples de demonstrar:

O próximo passo é considerar que sabendo resolver o problema para n-1 elementos, eu consigo também resolver para n:

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

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 ou em livros de algoritmos.
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.

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 :-)