Introdução à Recursão

Parte da seção Lógica & Fluxo do Journey de C++ da Coddy — lição 45 de 56.

A recursão é uma técnica de programação onde uma função chama a si mesma para resolver um problema. Em vez de usar loops, as funções recursivas decompõem problemas complexos em subproblemas menores e semelhantes até que alcancem um caso simples que pode ser resolvido diretamente.

Toda função recursiva deve ter dois componentes essenciais. O caso base é uma condição que interrompe a recursão - sem ele, a função chamaria a si mesma para sempre. O passo recursivo é onde a função chama a si mesma com parâmetros modificados, aproximando-se do caso base a cada chamada.

Aqui está um exemplo simples de contagem regressiva que demonstra recursão:

void countdown(int n) {
    if (n <= 0) {           // Caso base: para quando n chega a 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Passo recursivo: chama com n-1
}

Quando você chama countdown(3), ele imprime 3, depois chama countdown(2), que imprime 2, depois chama countdown(1), e assim por diante até atingir o caso base. Cada chamada de função espera que a próxima seja concluída antes de terminar, criando uma cadeia de chamadas que eventualmente retorna ao chamador original.

Folha de consulta

Recursão é quando uma função chama a si mesma para resolver um problema, dividindo-o em subproblemas menores.

Toda função recursiva precisa de:

Caso base: condição que interrompe a recursão
Passo recursivo: a função chama a si mesma com parâmetros modificados

Exemplo de função de contagem regressiva:

void countdown(int n) {
    if (n <= 0) {           // Caso base
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Passo recursivo
}

Experimente você mesmo

Esta lição não inclui um desafio de código.