Algoritmos C/C++

Recursão e pilha de chamadas em C e C++

Nesta lição, você vai calcular o fatorial com uma função recursiva e entender o caso base e o custo de memória da recursão.

Introdução

Recursão é a técnica de resolver um problema reduzindo-o a um problema menor do mesmo tipo. Toda função recursiva precisa de um caso base (base case), e cada chamada precisa chegar mais perto dele; caso contrário, o programa continua chamando a função para sempre.

Pontos importantes

Teste com entradas vazias, com um único elemento, com valores repetidos e já ordenadas.
Primeiro faça funcionar corretamente, depois otimize.
Em código real, prefira as funções prontas da biblioteca padrão.

Veja como funciona

Clique em Passo para seguir cada chamada. Novas chamadas entram na pilha de chamadas e cada uma devolve seu valor para quem a chamou.

Exemplos de código C e C++

Executar →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Resultado da execução

C++

Executar →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Resultado da execução

Comparação entre C e C++

A função factorial retorna 1 quando number é menor que 2, que é o caso base; caso contrário, retorna number * factorial(number - 1). Cada chamada ocupa mais um pedaço de memória na pilha de chamadas (call stack), então o algoritmo usa tempo O(n) e O(n) de pilha. A versão em C++ marca a função como constexpr, então o valor pode ser calculado já na compilação. Com entradas grandes, valide os dados e costume trocar a recursão por um laço.

Laços, ponteiros, tamanhos e buffers temporários são escritos explicitamente.

C++

Iteradores e algoritmos padrão separam o processamento da forma como os dados são guardados.

Exercícios práticos

Execute as duas versões e depois mude o código para observar a diferença de segurança que cada linguagem oferece.

Simule cada comparação no papel.
Teste com valores repetidos e com valores muito grandes e muito pequenos.
Meça o tempo do seu código e compare com a biblioteca padrão.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios