Implemente uma função que calcula o fatorial de determinado número (inteiro positivo) tanto iterativamente quanto recursivamente. Ou seja, mostre duas implementações para esta funcionalidade.

Passo 1

O que o enunciado pede:
  • Implementar uma função que calcule o fatorial de um número inteiro positivo.
  • Apresentar duas implementações: uma iterativa e outra recursiva.
Informações dadas (e decisões que vou assumir sem te perguntar):
  • A entrada é um número inteiro n.
  • Vou aceitar também n=0 como caso válido (já que por convenção 0! = 1).
  • Para n<0 vou tratar como erro (fatorial não está definido para inteiros negativos).
  • Vou cuidar de validação de tipo (se não for inteiro, também será tratado como erro).

Passo 2

Definição matemática do fatorial (para termos claros):
n! = \begin{cases} 1, & \text{se } n = 0,\\[4pt] n \cdot (n-1)!, & \text{se } n \ge 1. \end{cases}
Explicação das partes:
  • A expressão acima é uma definição por recorrência. O caso n=0 é o caso base, que impede recursão infinita e dá um valor inicial.
  • O caso n \ge 1 expressa o fatorial de n em termos do fatorial de n-1.]

Passo 3

Como funciona a solução recursiva (conceito passo a passo):
  • Ideia: implementar diretamente a definição. Para calcular n!, a função chama a si mesma para calcular (n-1)! e multiplica por n.
  • Componentes essenciais:
    • Caso base: se n = 0 (ou opcionalmente n=1) retornar 1.
    • Caso recursivo: retornar n \times \text{fatorial}(n-1).
  • Atenção prática: cada chamada recursiva empilha um quadro de chamada (stack). Para valores grandes de n isso pode estourar o limite de recursão da linguagem (por exemplo, em Python o limite padrão é ~1000 chamadas).
Exemplo manual com n=5 (mostrando a expansão recursiva):
5! = 5 \times 4! = 5 \times (4 \times 3!) = 5 \times 4 \times (3 \times 2!) = 5 \times 4 \times 3 \times (2 \times 1!) = 5 \times 4 \times 3 \times 2 \times 1! = 5 \times 4 \times 3 \times 2 \times 1 = 120.

Passo 4

Como funciona a solução iterativa (conceito passo a passo):
  • Ideia: multiplicar sequencialmente os inteiros de 1 até n, acumulando o resultado.
  • Algoritmo simples:
    • Começar com \text{resultado} \leftarrow 1.
    • Para k de 2 até n: \text{resultado} \leftarrow \text{resultado} \times k.
    • Retornar \text{resultado}.
  • Vantagens práticas: não usa pilha de chamadas, assim usa memória constante e é segura para valores de n bem maiores (limitada apenas pelo tempo e pela representação numérica).
Exemplo manual com n=5 (iterativo):
  • Inicialmente \text{resultado}=1.
  • Multiplica por 2: \text{resultado}=2.
  • Multiplica por 3: \text{resultado}=6.
  • Multiplica por 4: \text{resultado}=24.
  • Multiplica por 5: \text{resultado}=120.
  • Retorna 120.

Passo 5

Validação de entrada e detalhes práticos:
  • Verificar se o argumento é inteiro: se não for, lançar/indicar erro (por exemplo, em código lançar uma exceção).
  • Verificar se n \ge 0: se for negativo, indicar/lançar erro.
  • Complexidade de tempo: ambas as versões têm complexidade temporal \mathcal{O}(n).
  • Complexidade de espaço: versão iterativa \mathcal{O}(1) (apenas variáveis auxiliares); versão recursiva \mathcal{O}(n) por causa da pilha de chamadas.
  • Observação: muitas linguagens têm bibliotecas prontas (por ex. em Python existe math.factorial) — use-as em produção se disponíveis.

Passo 6

O que entregar (o que vou colocar na resposta final):
  • Duas funções implementadas (vou usar Python por ser claro e conciso):
    1. Uma função recursiva que segue a definição matemática e faz validação de entrada.
    2. Uma função iterativa que usa um laço e faz validação de entrada.
  • Cada função terá tratamento de entradas inválidas (tipo e sinal).
  • Exemplos de uso não serão repetidos nas etapas; estarão implícitos (ex.: chamar com 5 retorna 120; chamar com 0 retorna 1).

Resposta

def factorial_recursive(n):
    """
    Calcula o fatorial de n de forma recursiva.
    Entrada:
      n (int): inteiro >= 0
    Retorna:
      int: n!
    Levanta:
      TypeError: se n não for int
      ValueError: se n for negativo
    """
    if not isinstance(n, int):
        raise TypeError("n deve ser um inteiro")
    if n < 0:
        raise ValueError("n deve ser >= 0")
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)


def factorial_iterative(n):
    """
    Calcula o fatorial de n de forma iterativa.
    Entrada:
      n (int): inteiro >= 0
    Retorna:
      int: n!
    Levanta:
      TypeError: se n não for int
      ValueError: se n for negativo
    """
    if not isinstance(n, int):
        raise TypeError("n deve ser um inteiro")
    if n < 0:
        raise ValueError("n deve ser >= 0")
    result = 1
    k = 2
    while k <= n:
        result *= k
        k += 1
    return result

Exercícios relacionados