Fatorial com recursão em Python
Nesta lição, você vai escrever uma função recursiva para calcular o fatorial e entender o papel do caso base.
Introdução
O problema
Alguns problemas são descritos naturalmente por uma versão menor deles mesmos: uma pasta contém pastas, uma árvore genealógica contém árvores menores, n! é n vezes (n - 1)!. A recursão permite escrever código que segue essas definições diretamente.
Pense assim
A recursão é como uma fila de pessoas passando uma pergunta adiante. Para responder 6!, a primeira pessoa pergunta 5! para a próxima e fica esperando. Essa pessoa pergunta 4!, e assim por diante, até que alguém recebe a pergunta 1! e responde na hora. Aí cada resposta volta pela fila, e cada pessoa multiplica pelo seu próprio número.
factorial(6)🙋 A primeira pessoa: 6 × a resposta que ela está esperandonumber * factorial(number - 1)➡️ Faça a mesma pergunta para a próxima pessoa, com um número menorif number <= 1: return 1🛑 A última pessoa responde na hora: 1720⬅️ As respostas voltam pela fila: 720Uma função recursiva chama a si mesma com uma entrada menor até chegar a um caso base que ela responde diretamente. Aqui factorial(n) = n × factorial(n - 1) e factorial(1) = 1.
Pontos-chave
if number <= 1: return 1é o caso base; sem ele, as chamadas nunca parariam.return number * factorial(number - 1)chama a mesma função com um número menor.factorial(6)esperafactorial(5), que esperafactorial(4), atéfactorial(1).raise ValueError(...)rejeita números negativos, que senão nunca chegariam ao caso base.
Quando usar?
- Problemas definidos por versões menores: árvores, pastas, dados aninhados.
- Algoritmos de dividir para conquistar, como o merge sort.
- Aprender como funciona a pilha de chamadas.
Quando não é preciso
- Repetições simples como o fatorial em código real: um laço ou
math.factorialé mais rápido e não tem limite de profundidade. - Entradas muito profundas: o Python para em cerca de 1.000 chamadas aninhadas com RecursionError.
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.
Código de exemplo
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Resultado da execução
720
Explicação do código
Quando number é 0 ou 1, a função retorna 1 imediatamente. Esse é o caso base que impede a recursão de rodar para sempre. Para os outros valores, a função retorna number multiplicado por factorial(number - 1). Cada chamada recursiva fica guardada na pilha de chamadas (call stack), então a profundidade da recursão é O(n).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Esquecer o caso base
A função chama a si mesma para sempre até o Python lançar RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
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.
- Fatorial Multiplique todos os inteiros positivos até n. Fácil
- Recursive Power Compute a power recursively by halving the exponent. Médio