Ciências da computação dia 114

Nesta aula, mergulhamos no conceito de recursão, uma técnica de programação onde uma função chama a si mesma para resolver problemas que podem ser decompostos em subproblemas menores. A recursão é amplamente utilizada em algoritmos de busca, processamento de árvores, e problemas matemáticos. Vimos como a recursão pode tornar o código mais elegante, mas também requer cuidado com o uso da pilha de chamadas e com a definição correta do caso base.

O que é recursão?

Recursão é uma técnica onde uma função se refere a si mesma na sua definição. Uma analogia útil é a da boneca russa (matryoshka): cada boneca contém uma boneca menor dentro de si, até chegar ao menor boneco, que não pode ser aberto. Da mesma forma, um problema recursivo é resolvido resolvendo instâncias menores do mesmo problema até chegar a um caso trivial (caso base).

Por exemplo, para calcular o fatorial de um número n, podemos usar a definição recursiva: n! = n × (n-1)! para n > 0, e 0! = 1. Visualizamos isso como uma cadeia de multiplicações que se resolve de baixo para cima.

Componentes de uma função recursiva

Toda função recursiva deve ter dois elementos essenciais:

• Caso base: a condição de parada que retorna um valor diretamente, sem chamar a si mesma. Sem ele, a função nunca termina.
• Passo recursivo: a chamada da função com argumentos modificados, convergindo para o caso base.

Vejamos o exemplo do fatorial em Python:

def fatorial(n):
    if n == 0:  # caso base
        return 1
    else:
        return n * fatorial(n-1)  # passo recursivo

Note que o argumento n é decrementado a cada chamada até alcançar 0, garantindo a terminação.

Pilha de chamadas e Stack Overflow

Cada chamada recursiva adiciona um novo registro (frame) à pilha de chamadas (call stack). Esse registro armazena o ponto de retorno e as variáveis locais. Quando a função atinge o caso base, as chamadas começam a retornar, desempilhando os frames.

Se a recursão for muito profunda, a pilha pode estourar (stack overflow), causando um erro fatal. Em Python, o limite padrão é 1000 chamadas, mas pode ser alterado com sys.setrecursionlimit. Por isso, é importante controlar a profundidade da recursão.

Recursão vs Iteração

Muitos problemas podem ser resolvidos tanto recursivamente quanto iterativamente. A tabela abaixo compara as duas abordagens:

A escolha depende do contexto. Recursão pode ser mais intuitiva, mas iteração é preferível quando a profundidade é grande ou a eficiência é crítica.

Exemplo: Sequência de Fibonacci

A sequência de Fibonacci é definida como: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Sua implementação recursiva direta é:

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
>

Esta implementação tem complexidade exponencial O(2^n), pois recalcula os mesmos valores repetidamente. Para n=40, já são bilhões de chamadas. Uma melhoria é usar memoização (armazenar resultados em um cache) ou abordagem iterativa bottom-up, reduzindo a complexidade para O(n).

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
>

Essa técnica ilustra como podemos transformar uma recursão ineficiente em uma solução eficiente.

Recursão em cauda (Tail Recursion)

Uma recursão em cauda ocorre quando a chamada recursiva é a última operação da função, ou seja, o valor retornado pela chamada é imediatamente retornado sem processamento adicional. Em linguagens que otimizam tail calls, a recursão em cauda pode ser transformada em iteração, evitando o crescimento da pilha.

Exemplo de fatorial em cauda:

def fatorial_tail(n, acumulador=1):
    if n == 0:
        return acumulador
    return fatorial_tail(n-1, acumulador * n)

Note que a chamada recursiva é a última ação. Infelizmente, Python não realiza essa otimização, mas linguagens como Scheme, Haskell e algumas implementações de JavaScript suportam.

Aplicações comuns da recursão

A recursão é fundamental em diversas áreas da computação:

• Árvores: percurso em pré-ordem, em-ordem, pós-ordem.
• Grafos: busca em profundidade (DFS), componentes conectados.
• Backtracking: problemas de labirinto, N-rainhas, permutações.
• Algoritmos de divisão e conquista: mergesort, quicksort, busca binária.
• Expressões matemáticas: análise sintática, cálculo de derivadas simbólicas.

Dominar recursão é essencial para o pensamento computacional e para entrevistas técnicas.

Principais pontos

• Recursão resolve problemas dividindo-os em subproblemas menores.
• Toda função recursiva precisa de um caso base e um passo recursivo convergente.
• A pilha de chamadas tem tamanho limitado; recursões muito profundas causam stack overflow.
• Recursão em cauda é mais eficiente em linguagens que a otimizam.
• Para problemas com sobreposição de subproblemas, a memoização pode tornar a recursão viável.
• A iteração geralmente é mais eficiente em termos de memória e velocidade, mas a recursão pode ser mais clara.

Perguntas Frequentes

1. Qual a diferença entre recursão e iteração?

Recursão é uma técnica onde a função chama a si mesma, enquanto iteração usa estruturas de repetição (for, while). Recursão é mais adequada para problemas com estrutura hierárquica ou recursiva natural; iteração é preferível para processamento linear e quando o desempenho é crítico.

2. Recursão sempre é mais lenta que iteração?

Não necessariamente. Com otimizações como tail call elimination e memoização, a recursão pode ser tão eficiente quanto a iteração. No entanto, em linguagens sem essas otimizações, a recursão tende a ser mais lenta e consumir mais memória devido à pilha.

3. O que é stack overflow e como evitar?

Stack overflow ocorre quando a pilha de chamadas excede o limite de memória alocado. Para evitar, deve-se garantir que a recursão termina dentro de um número finito de chamadas, preferir recursão em cauda (se o compilador otimizar) ou usar iteração para problemas que exigem muitas repetições. Em Python, aumentar o limite com sys.setrecursionlimit é possível, mas não resolve o problema fundamental.