Aulas e o jogo de aprendizado

Recursão e backtracking

Funções que chamam a si mesmas, de uma contagem regressiva a um resolvedor de Sudoku, em um Raspberry Pi 4, com o limite real de profundidade do motor ensinado com honestidade.

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Memoização: as 21.891 chamadas do Fibonacci ingênuo para fib(20), um dicionário que reduz isso a 39, functools.lru_cache com suas contagens de acertos e erros, 601.080.390 rotas de rover por uma grade e as 242 formas de fazer um dólar.
  7. 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, ou RuntimeError: pystack exhausted para uma função com muitas variáveis locais. RecursionError, o nome do CPython, não está definido aqui. As aulas capturam RuntimeError, que funciona nos dois, porque o RecursionError do CPython é um tipo de RuntimeError.
  • 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.listdir e os conjuntos são ordenados antes de imprimir.
  • str.ljust e str.rjust nã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.