Factorial

Q: Qual é a complexidade de tempo do cálculo de um fatorial?

Tanto o loop quanto a recursão fazem uma multiplicação para cada número até n , então o tempo é O(n) . O loop precisa de espaço extra O(1) . A recursão mantém um quadro de pilha por chamada até que o caso base retorne, então usa espaço O(n) .

Q: Por que 0! é igual a 1?

0! é o produto de nenhum número, e um produto sem fatores é 1 , assim como uma soma sem parcelas é 0 . Isso também mantém válida a regra n! = n × (n-1)! para n = 1 : 1! = 1 × 0! = 1 . A contagem confirma: há exatamente uma maneira de organizar zero itens.

Q: Recursão ou um loop é melhor para calcular o fatorial?

Elas fazem as mesmas multiplicações e retornam a mesma resposta. A versão recursiva se parece com a definição matemática, por isso é um exercício clássico para começar a aprender recursão. O loop usa memória constante e não pode estourar a pilha de chamadas, então é a melhor opção em código real.

InicianteMatemática e simulação Recursão

+10

O fatorial de um número inteiro n, escrito como n!, é o produto de todos os números inteiros de 1 até n. Por exemplo, 4! = 1 × 2 × 3 × 4 = 24. Por definição, 0! = 1. Sua função recebe n e retorna n!.

Função

factorial(n: integer) → integer

ninteger: o número inteiro cujo fatorial você calcula
Retornainteger: o produto de todos os números inteiros de 1 a n, que é 1 quando n é 0

Restrições

0 ≤ n ≤ 12
A resposta cabe em um inteiro de 32 bits com sinal: o maior é 12! = 479001600.

Exemplos

Entrada: n = 5
Saída: 120
Explicação: Multiplique 1 × 2 × 3 × 4 × 5. O produto acumulado passa por 1, 2, 6, 24 e termina em 120.

Entrada: n = 0
Saída: 1
Explicação: Não há nada para multiplicar, e um produto sem fatores é 1. É por isso que 0! = 1.

Para ir além

100! tem 158 dígitos. Você consegue contar quantos zeros há no final dele sem calculá-lo?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

O fatorial tem duas descrições equivalentes, e cada uma delas se transforma em código. Como produto, n! = 1 × 2 × ... × n, que é um loop. Como definição recursiva, 0! = 1 e n! = n × (n-1)!, que é uma função que chama a si mesma. Ambas fazem cerca de n multiplicações. O loop é a opção para concluir, porque não precisa de pilha de chamadas.

Recursão a partir da definição

Intuição

O fatorial é definido por meio de um fatorial menor: n! = n × (n-1)!. Se você já sabe que 4! = 24, então 5! = 5 × 24 = 120. Uma função recursiva escreve essa frase como código. Para obter factorial(n), ela solicita factorial(n-1) e multiplica a resposta por n.

As chamadas precisam de um ponto de parada, o caso base: factorial(0) retorna 1 sem chamar nada. Cada chamada reduz n em um, então, a partir de 5, as chamadas seguem 5, 4, 3, 2, 1, 0. Então as respostas voltam pela cadeia: 1, 1, 2, 6, 24, 120.

Há n + 1 chamadas e n multiplicações, então o tempo é O(n). Cada chamada espera na pilha até que a chamada abaixo dela retorne, então a pilha armazena n + 1 quadros, o que corresponde a O(n) de espaço. Com n ≤ 12, isso é insignificante, mas o mesmo padrão com uma entrada grande estoura a pilha.

Algoritmo

Se n for 0, retorne 1. Esse é o caso base.
Caso contrário, chame a função com n-1.
Multiplique esse resultado por n e retorne-o.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Multiplicar em um loop

Intuição

Expanda a recursão e você obtém um produto acumulado. Comece com result = 1 e multiplique por 2, depois por 3, e assim por diante até n. Para n = 5, o resultado fica 1, 2, 6, 24, 120.

Começar em 1 também abrange as menores entradas. Para n = 0 e n = 1, o loop de 2 até n é executado zero vezes, e a função retorna o valor inicial 1, que é a resposta correta para ambos.

O loop realiza n-1 multiplicações, tem tempo O(n) e mantém um número, usando espaço O(1). Não há pilha de chamadas que possa transbordar, e é por isso que entrevistadores esperam essa versão depois que você apresenta a recursiva.

Algoritmo

Defina result = 1.
Percorra k de 2 até n, incluindo ambos.
Multiplique result por k a cada etapa.
Retorne result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Armadilhas e casos extremos

O código de fatorial é curto, então os bugs ficam nos casos extremos.

Começar o produto em 0. Cada multiplicação o mantém em 0. O valor inicial de um produto é 1.
Parar a recursão somente em n == 1. Se chamada com 0, essa função nunca alcança seu caso-base: continua com -1, -2 e assim por diante até a pilha transbordar. Faça de n == 0 o caso-base.
Repetir o laço com k < n em vez de k ≤ n. Isso deixa de fora o último fator e retorna (n-1)!, então 5 resulta em 24 em vez de 120.
Ignorar o overflow. 13! = 6227020800 não cabe em um inteiro com sinal de 32 bits. Em Java e C#, o produto sofre wrap silenciosamente e resulta em um número incorreto; em C, o overflow de inteiros com sinal tem comportamento indefinido; e uma compilação de depuração em Rust entra em panic. Um inteiro de 64 bits comporta até 20!; acima disso, você precisa de inteiros grandes.
Em Swift, escrever for k in 2...n. Um intervalo fechado cujo limite final é menor que o inicial causa uma falha em tempo de execução quando n é 0 ou 1.

Perguntas frequentes3

Qual é a complexidade de tempo do cálculo de um fatorial?

Tanto o loop quanto a recursão fazem uma multiplicação para cada número até n, então o tempo é O(n). O loop precisa de espaço extra O(1). A recursão mantém um quadro de pilha por chamada até que o caso base retorne, então usa espaço O(n).

Por que 0! é igual a 1?

0! é o produto de nenhum número, e um produto sem fatores é 1, assim como uma soma sem parcelas é 0. Isso também mantém válida a regra n! = n × (n-1)! para n = 1: 1! = 1 × 0! = 1. A contagem confirma: há exatamente uma maneira de organizar zero itens.

Recursão ou um loop é melhor para calcular o fatorial?

Elas fazem as mesmas multiplicações e retornam a mesma resposta. A versão recursiva se parece com a definição matemática, por isso é um exercício clássico para começar a aprender recursão. O loop usa memória constante e não pode estourar a pilha de chamadas, então é a melhor opção em código real.

def factorial(n):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

n = 5

Saída Esperada