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
. - Vou aceitar também
como caso válido (já que por convenção ). - Para
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):
Explicação das partes:
- A expressão acima é uma definição por recorrência. O caso
é o caso base, que impede recursão infinita e dá um valor inicial. - O caso
expressa o fatorial de em termos do fatorial de .]
Passo 3
Como funciona a solução recursiva (conceito passo a passo):
- Ideia: implementar diretamente a definição. Para calcular
, a função chama a si mesma para calcular e multiplica por . - Componentes essenciais:
- Caso base: se
(ou opcionalmente ) retornar . - Caso recursivo: retornar
.
- Caso base: se
- Atenção prática: cada chamada recursiva empilha um quadro de chamada (stack). Para valores grandes de
isso pode estourar o limite de recursão da linguagem (por exemplo, em Python o limite padrão é ~1000 chamadas).
Exemplo manual com
(mostrando a expansão recursiva):
Passo 4
Como funciona a solução iterativa (conceito passo a passo):
- Ideia: multiplicar sequencialmente os inteiros de
até , acumulando o resultado. - Algoritmo simples:
- Começar com
. - Para
de até : . - Retornar
.
- Começar com
- Vantagens práticas: não usa pilha de chamadas, assim usa memória constante e é segura para valores de
bem maiores (limitada apenas pelo tempo e pela representação numérica).
Exemplo manual com
(iterativo):
- Inicialmente
. - Multiplica por
: . - Multiplica por
: . - Multiplica por
: . - Multiplica por
: . - Retorna
.
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
: se for negativo, indicar/lançar erro. - Complexidade de tempo: ambas as versões têm complexidade temporal
. - Complexidade de espaço: versão iterativa
(apenas variáveis auxiliares); versão recursiva 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):
- Uma função recursiva que segue a definição matemática e faz validação de entrada.
- 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
retorna ; chamar com retorna ).
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