Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

De uma fila de pessoas para o código
factorial(6)🙋 A primeira pessoa: 6 × a resposta que ela está esperando
number * factorial(number - 1)➡️ Faça a mesma pergunta para a próxima pessoa, com um número menor
if number <= 1: return 1🛑 A última pessoa responde na hora: 1
720⬅️ As respostas voltam pela fila: 720
Cada chamada espera uma chamada menor até o caso base responder.
Em uma frase

Uma 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

  1. if number <= 1: return 1 é o caso base; sem ele, as chamadas nunca parariam.
  2. return number * factorial(number - 1) chama a mesma função com um número menor.
  3. factorial(6) espera factorial(5), que espera factorial(4), até factorial(1).
  4. 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

Executar código →
main.py
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))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Esquecer o caso base

A função chama a si mesma para sempre até o Python lançar RecursionError.

Problema
def factorial(number):
    return number * factorial(number - 1)
Correção
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.

Todos os desafios