재귀

"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는 리졸버 문제를 불연속적으로 활용하여 자연스러운 숫자를 포함합니다.
예를 들어, 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 é thinkar 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 problem as 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);
   }
}

카소 베이스: o arranjo é unitário eo elemento é igual ou diferente do valor buscado
히포테스 인두티바:
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 category 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.
Princípio da Indução Finita em suas várias formas equivalentes, pode ser encontrada em bons livros de análise 또는 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 evidencee no dia-a-dia :-)