Factorial
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
- 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 que0! = 1.
+11 testes ocultos ao enviar
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.
Escreva
4!e5!como produtos. Como5!está relacionado a4!?5! = 5 × 4!. Em geral,n! = n × (n-1)!, e a cadeia termina em0! = 1.Mantenha um produto acumulado que começa em
1e multiplique-o por cada número de2an. Começar em 1 também fornece a resposta correta para0e1.
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
nfor0, retorne1. Esse é o caso base. - Caso contrário, chame a função com
n-1. - Multiplique esse resultado por
ne 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
kde2atén, incluindo ambos. - Multiplique
resultporka 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 com0, essa função nunca alcança seu caso-base: continua com -1, -2 e assim por diante até a pilha transbordar. Faça den == 0o caso-base. - Repetir o laço com
k < nem vez dek ≤ n. Isso deixa de fora o último fator e retorna(n-1)!, então5resulta em 24 em vez de 120. - Ignorar o overflow.
13! = 6227020800nã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 quandoné 0 ou 1.
Perguntas frequentes4
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.
Qual é o maior fatorial que cabe em um inteiro?
12! = 479001600 é o maior fatorial que cabe em um inteiro com sinal de 32 bits. 20! = 2432902008176640000 é o maior para um inteiro com sinal de 64 bits. Além disso, você precisa de números de tamanho ilimitado, como int do Python, BigInteger do Java ou BigInt do JavaScript.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def factorial(n):
# Escreva o código aquiCaso 1
Caso 2
Entrada
n = 5
Esperado
120