Escreva a função P(x, y), que retorne x elevado a y, como:
a. Utilizando estrutura de repetição;
b. Utilizando recursividade;
c. Compare e explique os resultados.

Passo 1

Resumo do enunciado: precisamos criar uma função P(x, y) que calcule x elevado a y de duas formas diferentes (usando repetição e usando recursão) e depois comparar as abordagens.

Passo 2

Implementação usando estrutura de repetição: fazemos um laço que multiplica x por si mesmo y vezes, cuidando do caso y=0 que deve retornar 1.

Passo 3

Implementação usando recursividade: definimos o caso base y=0 retornando 1, e para y>0 retornamos x * P(x, y−1), fazendo com que a própria função se chame até chegar ao caso base.

Passo 4

Comparação das abordagens: analisamos legibilidade, uso de memória e riscos de stack overflow, além da diferença de complexidade prática e quando cada método é mais indicado.

Resposta

Função com repetição (Python):
def P_loop(x, y):
    # y deve ser inteiro não-negativo
    resultado = 1
    for _ in range(y):
        resultado *= x
    return resultado
Função recursiva (Python):
def P_rec(x, y):
    # y deve ser inteiro não-negativo
    if y == 0:
        return 1
    else:
        return x * P_rec(x, y - 1)
Comparação:
  • Legibilidade: a versão recursiva é mais curta e clara conceitualmente, mas pode confundir quem não está acostumado com recursão.
  • Uso de memória: o laço usa O(1) espaço extra, enquanto a recursão usa O(y) frames de pilha.
  • Performance: ambas têm tempo O(y), mas a recursiva pode ser ligeiramente mais lenta por causa das chamadas de função.
  • Riscos: se y for muito grande, a versão recursiva pode causar stack overflow; o laço não tem esse problema.
Em geral, para expoentes pequenos ou quando recusividade é aceita, P_rec é elegante; para expoentes grandes ou em sistemas com pilha limitada, P_loop é mais segura.

Exercícios relacionados