Recursão

Conceito

Recursão é uma função definida em termos de si mesma. Ela funciona quando o problema tem estrutura auto-similar: uma árvore é um nó com árvores, uma lista é um elemento seguido de uma lista, ordenar é ordenar duas metades.

Toda função recursiva correta tem duas partes, e as duas são obrigatórias:

1. caso base — a entrada em que você responde sem recorrer
2. passo recursivo — que reduz o problema e chama a si mesmo

O caso base errado é o bug mais comum, e ele se manifesta de duas formas: nunca ser alcançado (recursão infinita → estouro) ou responder errado no limite (fora-por-um que contamina todas as respostas).

Quando recursão é mais clara que iteração: quando o dado é recursivo. Travessia de árvore, parsing, backtracking, divide-and-conquer. O código espelha a definição do problema e cabe na cabeça.

Quando é pior: quando é um laço disfarçado. fatorial e soma de lista recursivos são exercícios, não código de produção — eles gastam O(n) de pilha para fazer o que um for faz com uma variável.

Memoização ataca um problema específico: subproblemas repetidos. Fibonacci ingênuo é O(2ⁿ) não porque é recursivo, mas porque recalcula fib(3) milhares de vezes. Guardando os resultados, cai para O(n). Isso é a porta de entrada da programação dinâmica — e o critério é: o mesmo subproblema aparece em mais de um lugar da árvore de chamadas? Se sim, memoize. Se não (como em travessia de árvore), não há nada para memoizar.

Recursão de cauda é quando a chamada recursiva é a última operação — nada acontece depois dela. Nesse caso o frame atual é inútil e poderia ser reusado. Linguagens com TCO convertem isso em laço; a maioria das linguagens imperativas não tem TCO.

Em Go

Go não faz tail-call optimization. Recursão em cauda gasta um frame como qualquer outra. Essa foi uma decisão consciente: TCO destrói stack traces, e Go prioriza depuração.

O que compensa isso é a stack elástica: a goroutine começa com 2 KB e cresce por cópia até 1 GB (2. Stack vs Heap). Na prática:

Ao estourar: fatal error: stack overflow, que não é recuperável com recover — o processo morre. Não existe "tratar" estouro de pilha em Go.

Memoização em Go é um map[K]V fechado numa closure, ou um campo de struct. Duas armadilhas específicas:

• concorrência: map não é seguro para escrita concorrente (fatal error: concurrent map writes). Memo compartilhado precisa de mutex.
• chave: precisa ser comparável (6. Hash Map). Para múltiplos parâmetros, uma struct como chave é o idioma — não concatenação de string.

Para o caso "calcule uma vez, muitos leitores", sync.OnceValue (Go 1.21+) resolve sem mapa nem mutex.

A recursão de função anônima exige declarar a variável antes, porque o nome não existe dentro do literal:

var dfs func(int)
dfs = func(n int) { ...; dfs(n-1) }

É um idioma que aparece constantemente em DFS e vale reconhecer de imediato.

Respostas às perguntas-guia

1. Qual é o caso base, e o que acontece se ele estiver errado?

Conceito: é a entrada respondida sem recorrer. Errado por ausência → recursão infinita; errado por valor → resposta errada em todos os níveis.

Em Go: recursão infinita não dá exceção tratável — dá fatal error: stack overflow, fatal e não recuperável. Em árvores, o caso base idiomático é o receiver nil, o que elimina a checagem no chamador.

2. Como você prova que a chamada recursiva se aproxima do caso base?

Conceito: nomeando uma medida que decresce estritamente e é limitada inferiormente. Se você não consegue nomeá-la, não sabe que termina.

Em Go: nada específico — mas em DFS de grafo a medida não é óbvia: o que garante terminação é o conjunto de visitados, não o tamanho da entrada (4. Grafos).

3. Quando recursão é mais clara que iteração — e quando é só mais lenta?

Conceito: mais clara quando o dado é recursivo (árvore, expressão, divisão). Só mais lenta quando é um for disfarçado.

Em Go: sem TCO, a versão recursiva de um laço simples é estritamente pior — mais frames, mesma lógica. Mas for também não é grátis de escrever: travessia de árvore iterativa exige gerenciar a pilha à mão.

4. O que é memoização e que problema ela ataca?

Conceito: cachear resultados por entrada, para atacar subproblemas repetidos. Só ajuda se o mesmo subproblema aparece mais de uma vez.

Em Go: map[K]V em closure. Para chave composta, struct. Para concorrência, mutex ou sync.OnceValue. E o ganho é dramático: fib(40) sai de segundos para microssegundos.

Trade-offs

Do conceito:

• Recursão compra clareza quando o dado é recursivo; cobra memória de pilha proporcional à profundidade.
• Memoização compra tempo e cobra memória — e adiciona a pergunta "quando invalidar".
• Iterativo compra controle e previsibilidade; cobra verbosidade e a chance de errar a gestão da pilha manual.

Em Go:

• Sem TCO: você paga frames por toda recursão. Em troca, o stack trace é fiel — e é isso que Go escolheu proteger.
• Stack de 1 GB torna a profundidade um não-problema para dados balanceados e um problema real para dados lineares ou degenerados.
• Estouro é fatal, não recuperável: você não pode se defender em runtime, só limitar a profundidade explicitamente.

Exemplo prático

package main

import (
	"fmt"
	"time"
)

// ---- O custo dos subproblemas repetidos ----
var chamadas int

func fibIngenuo(n int) int {
	chamadas++
	if n < 2 { return n } // caso base
	return fibIngenuo(n-1) + fibIngenuo(n-2)
}

// memo: map em closure. A chave precisa ser comparável.
func fibMemo() func(int) int {
	memo := map[int]int{}
	var f func(int) int
	f = func(n int) int { // recursão anônima: declare a var antes
		if n < 2 { return n }
		if v, ok := memo[n]; ok { return v }
		v := f(n-1) + f(n-2)
		memo[n] = v
		return v
	}
	return f
}

// ---- Memo com chave composta: struct, não string concatenada ----
type chave struct{ i, j int }

func caminhosGrade(m, n int) int {
	memo := map[chave]int{}
	var f func(int, int) int
	f = func(i, j int) int {
		if i == 0 || j == 0 { return 1 }
		k := chave{i, j}
		if v, ok := memo[k]; ok { return v }
		v := f(i-1, j) + f(i, j-1)
		memo[k] = v
		return v
	}
	return f(m, n)
}

// ---- A medida que decresce: sem ela, não termina ----
func passosAte1(n int) int { // medida: n, decresce por metade, limitada em 1
	if n <= 1 { return 0 }
	return 1 + passosAte1(n/2)
}

func main() {
	t := time.Now()
	chamadas = 0
	fmt.Printf("fib(30) ingênuo = %d em %d chamadas (%v)\n",
		fibIngenuo(30), chamadas, time.Since(t).Round(time.Millisecond))

	memo := fibMemo()
	t = time.Now()
	fmt.Printf("fib(90) memoizado = %d (%v)\n", memo(90), time.Since(t))

	fmt.Println("caminhos numa grade 10x10:", caminhosGrade(10, 10))
	fmt.Println("passos para 1024 chegar a 1:", passosAte1(1024)) // 10 = log2

	// profundidade segura vs arriscada
	fmt.Println("recursão de profundidade 100k:", somaAte(100_000) > 0)
}

func somaAte(n int) int {
	if n == 0 { return 0 }
	return n + somaAte(n-1) // 100k frames: cabe na stack elástica
}

fib(30) ingênuo faz mais de 2,6 milhões de chamadas; memoizado, fib(90) faz 90. A diferença não é recursão contra iteração — é recalcular contra lembrar.

Relacionado

• 6. Pilha de Chamadas — o que cada chamada custa
• 3. Travessias de Árvore — recursão onde ela é a ferramenta certa
• 4. Grafos — recursão onde a terminação vem dos visitados, não da medida
• 2. Merge Sort — semana 4, divide-and-conquer e o teorema mestre na prática
• 2. Stack vs Heap — semana 1, por que profundidade é memória

---

Parte de Semana 03 - Estruturas de Dados II e Recursão · 00 - MOC Fundamentos de Programação