Nesta aula, abordamos o conceito de recursão e os algoritmos de divisão e conquista, duas técnicas fundamentais para a resolução de problemas computacionais. Vimos exemplos práticos, analisamos a complexidade e discutimos quando utilizar cada abordagem.

1. O que é Recursão?

Recursão é uma técnica onde uma função chama a si mesma para resolver um problema menor, até atingir um caso base. É amplamente utilizada em problemas que podem ser decompostos em subproblemas semelhantes ao original.

Por exemplo, o cálculo do fatorial de um número n (n!) pode ser definido recursivamente como: n! = n × (n-1)!, com caso base 0! = 1.

2. Componentes de uma Função Recursiva

Toda função recursiva deve possuir:

  • Caso base: condição que interrompe a recursão.
  • Passo recursivo: chamada à própria função com argumentos simplificados.

Sem um caso base, a recursão se tornaria infinita, resultando em estouro de pilha (stack overflow).

3. Exemplos Práticos

Fatorial

def fatorial(n):
    if n == 0:
        return 1
    else:
        return n * fatorial(n - 1)

Para n=4, a sequência de chamadas é: fatorial(4) → 4 × fatorial(3) → 4 × 3 × fatorial(2) → 4 × 3 × 2 × fatorial(1) → 4 × 3 × 2 × 1 × fatorial(0) → 24.

Sequência de Fibonacci

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

A implementação recursiva ingênua de Fibonacci tem complexidade exponencial, sendo ineficiente para n grandes. Por isso, em muitos casos, a versão iterativa é preferível.

4. Recursão vs Iteração

Recursão pode tornar o código mais legível e próximo da definição matemática, mas pode consumir mais memória devido à pilha de chamadas. Iteração, por outro lado, é geralmente mais eficiente em termos de tempo e espaço, mas pode ser menos intuitiva para problemas naturalmente recursivos.

5. Divisão e Conquista

A técnica de divisão e conquista consiste em dividir um problema em subproblemas menores, resolver cada um recursivamente e combinar as soluções. Essa abordagem é a base de algoritmos eficientes como Merge Sort, Quick Sort e Busca Binária.

6. Busca Binária

Busca binária é um algoritmo de divisão e conquista que encontra um elemento em uma lista ordenada em O(log n). Divide a lista ao meio e descarta a metade que não contém o elemento.

def busca_binaria(arr, alvo, esquerda, direita):
    if esquerda > direita:
        return -1
    meio = (esquerda + direita) // 2
    if arr[meio] == alvo:
        return meio
    elif arr[meio] < alvo:
        return busca_binaria(arr, alvo, meio + 1, direita)
    else:
        return busca_binaria(arr, alvo, esquerda, meio - 1)

7. Merge Sort

Merge Sort divide a lista ao meio recursivamente até obter listas de um elemento (ordenadas por definição) e depois intercala (merge) as listas ordenadas para formar a lista final.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Complexidade: O(n log n) no pior caso. É estável e previsível, mas requer memória extra para as sublistas.

8. Quick Sort

Quick Sort escolhe um pivô, particiona a lista em elementos menores e maiores que o pivô, ordena recursivamente as partições e combina.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivo = arr[0]
    menores = [x for x in arr[1:] if x <= pivo]
    maiores = [x for x in arr[1:] if x > pivo]
    return quick_sort(menores) + [pivo] + quick_sort(maiores)

Complexidade: O(n log n) caso médio, O(n²) pior caso (quando o pivô é mal escolhido). No entanto, com boas escolhas de pivô (mediana de três), o pior caso é raro. Quick Sort é geralmente mais rápido na prática que Merge Sort para arrays pequenos e sem restrições de memória.

9. Análise de Complexidade

Entender a complexidade dos algoritmos recursivos é essencial. A análise pode ser feita através de relações de recorrência. Por exemplo, para Merge Sort: T(n) = 2T(n/2) + O(n), cuja solução é O(n log n). Já para o fatorial, T(n) = T(n-1) + O(1) → O(n).

A recorrência de Fibonacci ingênua é T(n) = T(n-1) + T(n-2) + O(1), resultando em O(2^n), o que motiva o uso de programação dinâmica.

10. Perguntas Frequentes

Qual a diferença entre recursão e iteração?
Recursão é quando uma função chama a si mesma; iteração é repetição com laços (for, while). Recursão pode ser mais expressiva, mas iteração é geralmente mais eficiente.

Quando usar recursão?
Quando o problema pode ser naturalmente dividido em subproblemas menores e a solução recursiva é mais simples de entender e manter.

O que é stack overflow em recursão?
Ocorre quando as chamadas recursivas excedem a profundidade máxima da pilha de execução. Pode ser evitado com recursão de cauda (tail recursion) ou com limites adequados.

Qual a vantagem do Merge Sort sobre o Quick Sort?
Merge Sort tem complexidade O(n log n) garantida e é estável, mas requer memória extra. Quick Sort é in-place (com cuidado) e geralmente mais rápido, mas pode ter pior caso O(n²).

O que é divisão e conquista?
É uma estratégia algorítmica que divide o problema em partes menores, resolve cada parte recursivamente e combina os resultados.

Conclusão

Nesta aula, vimos que recursão e divisão e conquista são ferramentas poderosas para construir algoritmos elegantes e eficientes. Compreender seus fundamentos e saber analisar a complexidade permite escolher a melhor abordagem para cada problema.

Para mais notas de aula, visite a página de Posts ou navegue pelas tags.