Fatorial Recursivo

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

O fatorial de um número é um exemplo perfeito para demonstrar a recursão em ação. O fatorial de n (escrito como n!) é o produto de todos os números inteiros positivos de 1 a n. Por exemplo, 5! = 5 × 4 × 3 × 2 × 1 = 120.

O que torna o fatorial ideal para a recursão é que ele pode ser definido em termos de si mesmo: n! = n × (n-1)!. Isso significa que para calcular 5!, você multiplica 5 por 4!, e para calcular 4!, você multiplica 4 por 3!, e assim por diante.

Aqui está como uma função fatorial recursiva se parece:

int factorial(int n) {
    if (n <= 1) {           // Caso base: 0! e 1! são ambos iguais a 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Passo recursivo: n! = n × (n-1)!
}

O caso base interrompe a recursão quando n atinge 1 ou 0, retornando 1. O passo recursivo multiplica o número atual pelo fatorial do próximo número menor. Quando você chama factorial(4), ele calcula 4 × 3 × 2 × 1 fazendo chamadas sucessivas até atingir o caso base, e então multiplica todos os resultados à medida que as chamadas retornam.

Desafio

Fácil

Crie um programa que implemente uma função fatorial recursiva e a utilize para calcular fatoriais para diferentes valores de entrada. Este desafio testará sua compreensão de como a recursão funciona, fazendo com que uma função chame a si mesma com parâmetros modificados até atingir um caso base.

A seguinte entrada será fornecida:

Um número inteiro n representando o número para o qual o fatorial deve ser calculado

Seu programa deve:

Criar uma função recursiva chamada factorial que recebe um parâmetro inteiro e retorna um inteiro
A função deve implementar o caso base: se n for menor ou igual a 1, retornar 1
A função deve implementar o passo recursivo: retornar n multiplicado pelo fatorial de n-1
Na função principal, ler o valor de entrada
Chamar a função fatorial com o valor de entrada
Imprimir o resultado usando o formato especificado

Use o seguinte formato de saída exato:

Factorial of [n] is [result]

Lembre-se de que a função fatorial deve chamar a si mesma com um valor menor a cada vez, aproximando-se do caso base a cada chamada recursiva. O caso base evita a recursão infinita ao parar quando n atinge 1 ou 0. O passo recursivo multiplica o número atual pelo fatorial do próximo número menor, construindo o resultado final à medida que as chamadas de função retornam seus valores.

Folha de consulta

O fatorial de n (n!) é o produto de todos os números inteiros positivos de 1 a n. Ele pode ser definido recursivamente como: n! = n × (n-1)!

Função fatorial recursiva:

int factorial(int n) {
    if (n <= 1) {           // Caso base: 0! e 1! são ambos iguais a 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Passo recursivo: n! = n × (n-1)!
}

O caso base interrompe a recursão quando n atinge 1 ou 0. O passo recursivo multiplica o número atual pelo fatorial do próximo número menor.

Experimente você mesmo

#include <iostream>
using namespace std;

// TODO: Escreva sua função fatorial aqui

int main() {
    // Ler a entrada
    int n;
    cin >> n;
    
    // TODO: Chame a função fatorial e armazene o resultado
    
    // Exibir o resultado
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}

Teste seus conhecimentos

Esta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.

Todas as lições de Lógica & Fluxo

3Projeto: Ferramenta de Lista de Tarefas

Visão Geral do Projeto Adicionando uma Tarefa

Visualizando Tarefas

Removendo uma Tarefa

Finalizando a Ferramenta

6Conjuntos (Elementos Únicos)

Apresentando o std::set Criar Conjunto e Adicionar Elementos Verificando Elementos Removendo Elementos Iterando sobre um Conjunto Recapitulação - Números Únicos

9Desafios Finais

Filtragem de Dados em Vetores Busca de Valores em Mapas Ponteiro e Array Dinâmico