Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Recursão

A recursão consiste em uma função se chamar a si própria, diretamente ou através de outras funções. Para o cálculo terminar, precisa de um caso base alcançável e de passos recursivos que avancem em direção a esse caso.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

A recursão (recursion) é uma técnica em que uma função se chama a si própria, direta ou indiretamente através de outras funções. Não requer uma palavra-chave especial: utiliza a sintaxe normal de chamada de funções. C++ permite chamadas recursivas, mas main não pode ser chamada recursivamente.

Um algoritmo típico tem um caso base, que devolve um resultado sem fazer outra chamada, e um passo recursivo, que reduz o problema. Para os dados cujo cálculo deve terminar, cada cadeia de chamadas tem de chegar a um caso base. Ter apenas uma condição de paragem não é suficiente se os argumentos nunca a satisfizerem.

No exemplo, sum_to(5) calcula a soma de 1 a 5, inclusive. As chamadas diminuem n até este chegar a 0; os retornos sucessivos somam então os valores pendentes, produzindo 15. Cada invocação tem o seu próprio parâmetro n; não se trata de uma única variável partilhada. Para n <= 0, a função devolve 0.

Não consideres o exemplo uma solução para dados de tamanho arbitrário: uma recursão profunda pode esgotar os recursos de execução, e uma soma fora do intervalo de int causa comportamento indefinido. Para dados grandes, considera um ciclo e verificações de intervalo. A fonte indicada é um projeto de norma em evolução, não uma publicação C++23 definitiva; o exemplo utiliza sintaxe compatível com C++23.

Exemplos

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Resultado

15

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes