O curso
Recursion and backtracking é um curso intermediário de Programação em sete aulas, depois de Python do zero e Conserte o bug. A maior parte roda na montagem do Pi com dois LEDs da galeria (vermelho no GPIO17, amarelo no GPIO27), e o chefão usa o módulo de semáforo. Cada passo é conferido com o que o Pi imprime ou o que seus pinos fazem, e todo número nas aulas é um que o programa realmente imprime.
- Chamadas que chamam a si mesmas: uma contagem regressiva sem loop, a pilha de chamadas desenhada como indentação enquanto cresce e encolhe, fatorial com inteiros grandes exatos (25! completo), um triângulo de Sierpinski impresso como texto e um LED piscando cinco vezes por recursão.
- Casos-base: um mergulho numa caverna sem fundo que transborda a pilha, um caso-base que interrompe isso, o limite de profundidade medido (um pouco menos de 1.000 chamadas para uma função pequena), exponenciação por quadrados (2^100 em 8 chamadas) e por que uma linha reta de trabalho pertence a um loop.
- Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
- Permutações: cada ordem de uma tripulação, n! contado até 720, um sinal alienígena embaralhado decodificado contra uma lista de palavras, cargas de rover embaladas com o padrão incluir-ou-pular, e o resultado conferido com
itertools.permutations. - Backtracking: N damas com escolher, explorar, desescolher; toda solução contada de 4 a 8 (92 para o tabuleiro de xadrez); 15.720 quadrados verificados em vez de 16 milhões de tabuleiros; o LED amarelo piscando a cada backtrack; e um labirinto de caverna marinha do qual se escapa.
- Memoização: as 21.891 chamadas do Fibonacci ingênuo para fib(20), um dicionário que reduz isso a 39,
functools.lru_cachecom suas contagens de acertos e erros, 601.080.390 rotas de rover por uma grade e as 242 formas de fazer um dólar. - Chefão: um solucionador de Sudoku: o final.
O gran final
O chefão constrói um solucionador de Sudoku completo em cerca de vinte linhas. Ele carrega um quebra-cabeça de verdade, escreve as regras como uma função e testa numa primeira célula, depois resolve a grade por backtracking: ache a primeira célula vazia, tente cada dígito que couber, resolva o resto e desfaça o dígito se isso falhar. Uma verificação independente prova que toda linha, coluna e bloco contém 1 a 9 (4.208 posicionamentos para esse quebra-cabeça), os semáforos ficam amarelos enquanto ele pensa e verdes quando está resolvido, e uma guarda deixa a luz vermelha para um quebra-cabeça que quebra as regras antes que o solucionador perca um segundo com ele.
O que o motor do Pi faz de diferente
O Pi roda MicroPython 1.29, não CPython, e a recursão é onde isso mais aparece:
- Uma recursão profunda demais levanta
RuntimeError: maximum recursion depth exceeded, ouRuntimeError: pystack exhaustedpara uma função com muitas variáveis locais.RecursionError, o nome do CPython, não está definido aqui. As aulas capturamRuntimeError, que funciona nos dois, porque oRecursionErrordo CPython é um tipo deRuntimeError. - O limite é a memória da pilha, não uma contagem fixa: cerca de 980 chamadas para uma função minúscula, menos para uma maior. Não existe
sys.setrecursionlimit. - Os dicts não guardam a ordem em que as chaves entraram, então as árvores são guardadas como listas e tuplas, e
os.listdire os conjuntos são ordenados antes de imprimir. str.ljustestr.rjustnão existem, então o preenchimento é feito com" " * count. Inteiros não têm limite de tamanho, como no CPython.
Todo o resto do curso, functools.lru_cache, itertools e os, roda como num Pi de verdade.