Dividir para conquistar
Uma técnica recursiva para resolver problemas: (1) descubra o caso base mais simples; (2) reduza o problema até ele virar o caso base. O quicksort usa essa técnica. Aqui estão os dois exemplos que o livro usa para introduzi-la.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
// Terreno de a × b: o lado do maior quadrado que o divide por igual é o MDC
function mdc(a, b) {
if (b === 0) return a; // caso base: sobrou só quadrados
return mdc(b, a % b); // caso recursivo: repete com o que sobrou
}
// Soma de uma lista: primeiro item + soma do resto
function soma(lista) {
if (lista.length === 0) return 0; // caso base
const [primeiro, ...resto] = lista;
return primeiro + soma(resto); // caso recursivo
}1. O terreno e o algoritmo de Euclides
Divida um terreno retangular em quadrados iguais, os maiores possíveis. Caso base: quando um lado divide o outro, o terreno já é feito de quadrados iguais. Senão, corte o maior quadrado que cabe e repita com a sobra. O lado final é o maior divisor comum (MDC) das duas medidas.
2. Soma recursiva de uma lista
Caso base: a lista vazia soma 0. Caso recursivo: o primeiro item mais a soma do resto. A recursão desce até a lista vazia e depois os resultados voltam somando.
- soma([2, 4, 6]) = 2 + soma([4, 6]) = 12
- soma([4, 6]) = 4 + soma([6]) = 10
- soma([6]) = 6 + soma([]) = 6
- soma([]) = 0 (caso base)