Pular para o conteúdo
</> Entendendo Algoritmos

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.

  1. soma([2, 4, 6]) = 2 + soma([4, 6]) = 12
  2. soma([4, 6]) = 4 + soma([6]) = 10
  3. soma([6]) = 6 + soma([]) = 6
  4. soma([]) = 0 (caso base)