3.2 Dividir para Conquistar

Toda função recursiva que se preze precisa de duas coisas para não destruir a memória: saber quando parar e saber como diminuir o problema.

Essas duas regras de ouro recebem nomes super importantes na programação: Caso Base e Caso Recursivo.

O Caso Base

O Caso Base é o freio de emergência da recursão. É a condição que avisa a função: “Pronto, o problema está tão pequeno que já sabemos a resposta. Pare de chamar a si mesma”.

Sem ele, a função entra em loop infinito e causa um Stack Overflow. O Caso Base é o limite absoluto, a menor das Matrioskas, o ponto onde não dá mais para quebrar nada.

O Caso Recursivo

Aqui é onde a mágica acontece. A função chama a si mesma, mas com um detalhe crucial: ela precisa passar adiante um pedaço MENOR do problema original.

Se ela tentar resolver exatamente a mesma coisa repetidas vezes, nunca sairá do lugar. A ideia de “Dividir para Conquistar” (Divide and Conquer) significa que, a cada repetição, o problema original vai sendo fatiado e encolhido até bater inevitavelmente no Caso Base.

Contagem Regressiva na Prática

Vamos ver as duas regras em ação num código simples que faz uma contagem regressiva para o lançamento de um foguete:

def contagem_regressiva(numero):
    # 1. CASO BASE
    if numero == 0:
        print("Lançar Foguete! 🚀")
        return

    # 2. CASO RECURSIVO
    print(numero)
    contagem_regressiva(numero - 1)

Olhe o que acontece na Pilha de Chamadas quando executamos contagem_regressiva(3):

1. O valor 3 não é igual a zero. Então o computador imprime 3.
   contagem_regressiva(3)
2. A função chama ela mesma passando 3 - 1. O problema encolheu!
   contagem_regressiva(3)

   contagem_regressiva(2)
3. Na próxima etapa da pilha, o novo valor 2 também não cai no Caso Base. Imprime 2.
4. Chama de novo passando 1.
   contagem_regressiva(3)

   contagem_regressiva(2)

   contagem_regressiva(1)
5. Na última volta, a função recebe 0. O Caso Base é atingido! Ela imprime a mensagem e bate num return.
   contagem_regressiva(3)

   contagem_regressiva(2)

   contagem_regressiva(1)

   contagem_regressiva(0)

É esse return final que avisa o computador que a missão acabou. A partir daí, a função 0 é removida da memória, o que encerra a função 1, que encerra a 2, e finalmente a 3. Como um efeito dominó, todos os “pratos” são desempilhados e a memória volta a ficar limpa.

A Ponte para a Ordenação Rápida

Lembra dos algoritmos que vimos no Capítulo 2 (Bubble, Selection, Insertion)? Eles esbarravam na barreira do \( O(n^2) \) porque tentavam ordenar a lista inteira de uma vez através de loops repetitivos e exaustivos.

Os algoritmos mais avançados que vamos aprender no Capítulo 4 usam o Dividir para Conquistar. Em vez de tentar ordenar 1.000 itens de uma vez, eles dividem a lista pela metade sucessivas vezes, até sobrarem listas minúsculas de 1 único item (o nosso Caso Base!). E adivinha? Uma lista de 1 item já está ordenada por natureza.

Depois, eles só precisam colar os pedaços de volta.

Com a Recursividade dominada, você tem a chave de ouro em mãos. Vamos conhecer a verdadeira eficiência do Merge Sort e do Quick Sort no Capítulo 4?