O que é recursão?

Algoritmos básicos recursivos

Fatorial

function fatorial(n) {
  if (n === 0 || n === 1) {
    return 1; // Caso base
  } else {
    return n * fatorial(n - 1); // Chamada recursiva
  }
}

console.log(fatorial(5)); // Saída: 120

Perceba como a função fatorial chama a si mesma com n - 1 até que n seja 0 ou 1.

Sequência de Fibonacci

def fibonacci(n):
    if n <= 1:
        return n  # Caso base
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # Chamadas recursivas

print(fibonacci(7))  # Saída: 13

Aqui, a função fibonacci chama a si mesma duas vezes, reduzindo o problema a somas de números menores na sequência.

Busca binária

function buscaBinaria(array, valor, inicio = 0, fim = array.length - 1) {
  if (inicio > fim) {
    return -1; // Valor não encontrado
  }

  let meio = Math.floor((inicio + fim) / 2);

  if (array[meio] === valor) {
    return meio; // Valor encontrado
  } else if (array[meio] > valor) {
    return buscaBinaria(array, valor, inicio, meio - 1); // Busca na metade esquerda
  } else {
    return buscaBinaria(array, valor, meio + 1, fim); // Busca na metade direita
  }
}

const numeros = [1, 3, 5, 7, 9, 11];
console.log(buscaBinaria(numeros, 7)); // Saída: 3

A função buscaBinaria divide o array continuamente até encontrar o valor ou concluir que ele não está presente.

Torres de Hanoi

def torres_de_hanoi(n, origem, destino, auxiliar):
    if n == 1:
        print(f"Mova o disco 1 de {origem} para {destino}")
        return
    torres_de_hanoi(n-1, origem, auxiliar, destino)
    print(f"Mova o disco {n} de {origem} para {destino}")
    torres_de_hanoi(n-1, auxiliar, destino, origem)

torres_de_hanoi(3, 'A', 'C', 'B')

A função torres_de_hanoi resolve o problema movendo discos entre as hastes de forma recursiva.

Por que a recursão é importante?

Elegância e simplicidade

Dividir para conquistar

Aplicações na vida real

• Inteligência artificial: algoritmos como minimax em jogos de tabuleiro utilizam recursão para prever movimentos.

• Processamento de imagens: fractais e algoritmos de preenchimento usam recursão para repetir padrões.

• Sistemas operacionais: navegação em sistemas de arquivos, onde pastas podem conter outras pastas.

Vamos codar juntos?

O conceito por trás do merge sort

1. Divisão: divide a lista original em duas metades aproximadamente iguais.

2. Conquista: ordena recursivamente as duas metades.

3. Combinação: mescla as duas metades ordenadas em uma única lista ordenada.

Passo a passo do algoritmo

Passo 1: dividir o array

function mergeSort(array) {
  if (array.length <= 1) {
    return array; // Caso base: array de tamanho 0 ou 1 já está ordenado
  }

  const meio = Math.floor(array.length / 2);
  const esquerda = array.slice(0, meio);
  const direita = array.slice(meio);

  // Chamada recursiva para cada metade
  return merge(mergeSort(esquerda), mergeSort(direita));
}

Passo 2: ordenar recursivamente as metades

• Caso base: quando o array tem tamanho 0 ou 1, ele é retornado como está.

• Chamada recursiva: a função continua dividindo as metades até chegar ao caso base.

Passo 3: mesclar os arrays ordenados

function merge(esquerda, direita) {
  let resultado = [];
  let indiceEsquerda = 0;
  let indiceDireita = 0;

  while (indiceEsquerda < esquerda.length && indiceDireita < direita.length) {
    if (esquerda[indiceEsquerda] < direita[indiceDireita]) {
      resultado.push(esquerda[indiceEsquerda]);
      indiceEsquerda++;
    } else {
      resultado.push(direita[indiceDireita]);
      indiceDireita++;
    }
  }

  // Concatena os elementos restantes
  return resultado
    .concat(esquerda.slice(indiceEsquerda))
    .concat(direita.slice(indiceDireita));
}

Passo 4: testar o algoritmo com a lista da Fernanda

const participantes = ['Diego', 'Mayk', 'Larissa', 'Fernanda', 'Ana', 'Bruno'];

console.log(mergeSort(participantes));
// Saída: ['Ana', 'Bruno', 'Diego', 'Fernanda', 'Larissa', 'Mayk']

Visualizando o processo de ordenação

['Diego', 'Mayk', 'Larissa'] | ['Fernanda', 'Ana', 'Bruno']

Por que a recursão é essencial aqui?

• Divisão recursiva: a função se chama para dividir o array até chegar ao caso base.

• Mesclagem ordenada: a combinação dos subarrays é feita de forma ordenada, garantindo a ordenação final.

Com esse passo a passo detalhado, a Fernanda pode usar o Merge Sort para organizar eficientemente qualquer lista, garantindo que tudo esteja em ordem para os eventos da Rocketseat. E você, pronto para implementar o Merge Sort nos seus projetos?

Materiais para aprimorar seus conhecimentos

Cursos gratuitos: comece sua jornada hoje mesmo

Transforme sua carreira com a formação Full-Stack

O que você vai encontrar:

• Mais de 44 horas de conteúdo gravado, com aulas ministradas por Mayk Brito e Rodrigo Gonçalves.

• Certificado validado pelo mercado ao final da formação.

• Acompanhamento personalizado, com tutoria, mentorias de carreira e eventos de networking.

• Projetos profissionais para enriquecer seu portfólio e preparar você para desafios reais.

Tecnologias ensinadas:

• JavaScript, TypeScript, HTML, CSS, React.js e Node.js, com aulas práticas e exemplos do mundo real.