Aula 15: Recursão, backtracking e introdução a DP
Você chegou ao capstone — muito bem! Vamos começar com uma matrioska: uma boneca com uma boneca menor dentro, até chegar à minúscula que não abre mais. Isso é exatamente 'recursão': uma função que chama a si mesma numa versão menor do mesmo problema, e a boneca que não abre é o 'caso base' que inter
Recursão é como uma matrioska russa: cada boneca abre uma menor, até chegar à minúscula que não abre (o caso base). Backtracking é tentar um caminho, e se for um beco sem saída — fechá-lo e tentar outro. Memoização é anotar respostas que você já calculou, para não calculá-las de novo.
- recursão e backtracking
- Recursão: uma função que chama a si mesma num subproblema menor até um caso base. Backtracking: tente uma escolha, chame recursivamente, e desfaça a escolha para explorar todas as possibilidades.
- caso base
- A condição que interrompe a recursão e retorna uma resposta direta sem outra chamada — sem ela a recursão nunca termina.
- memoização
- Guardar em cache os resultados de subproblemas (por exemplo, num dict) para que não sejam recalculados — isso evita trabalho repetido e pode acelerar drasticamente as coisas (por exemplo, o Fibonacci ingênuo de O(2ⁿ) para O(n)).
