Considere a função \boldsymbol{\operatorname { p o t }} \boldsymbol{(} \boldsymbol{n}, \boldsymbol{k})=\boldsymbol{n}^{\boldsymbol{k}} e o seguinte cabeçalho desta função escrito na linguagem C:
int pot( int n, int k ) {
}
Escreva a função pot de forma recursiva.

Passo 1

O enunciado pede: implementar de forma recursiva a função que calcula \operatorname{pot}(n,k)=n^{k} dado o cabeçalho em C
int pot( int n, int k ) {
}
Informações dadas e suposições que vou usar (não perguntei nada porque você pediu a implementação direta):
  • A função deve devolver um inteiro (tipo int).
  • A definição matemática é \operatorname{pot}(n,k)=n^{k}.
  • Vou assumir que k é um inteiro não negativo ( k\ge 0). Se k<0 o resultado é uma fração e não cabe num int; então essa situação não será completamente suportada por essa versão (vou tratar isso explicitamente no código).
  • Tratamento de 0^{0}: é um caso ambíguo em matemática, mas em muitas implementações de programação é conveniente definir 0^{0}=1; essa implementação seguirá essa convenção para simplificar.

Passo 2

Conceito essencial: recursão.
  • Recursão é quando uma função chama a si mesma para resolver subproblemas menores.
  • Para usar recursão precisamos de:
    1. Um caso base (quando parar de recursar).
    2. Um passo recursivo que reduz o problema até atingir o caso base.
No nosso problema, a redução natural vem da propriedade dos expoentes:
n^{k} = n \cdot n^{k-1}\quad\text{para }k>0.
E o caso base natural é:
n^{0}=1.

Passo 3

Definindo o caso base e a condição de validade:
  • Caso base: se k=0 retornamos 1 porque n^{0}=1 para qualquer n (seguindo a convenção para 0^{0}).
  • Validade: se k<0 não podemos representar n^{k} (fração) com retorno int. Vou detectar esse caso e devolver um valor sentinela (por exemplo 0) ou você poderia optar por tratar com double em outra versão. Aqui só aviso que retornarei 0 para indicar não suporte a expoente negativo; e também colocarei um comentário no código explicando isso.

Passo 4

Escrevendo o passo recursivo:
  • Para k>0 usamos a definição recursiva:
n^{k} = n \cdot n^{k-1}.
  • Em C, traduzimos isso por return n * pot(n, k-1);.
  • Atenção aos limites: se k for grande, haverá muitas chamadas recursivas (profundidade k) e risco de estouro de pilha; além disso, o resultado pode estourar o tipo int. Essas são limitações práticas.

Passo 5

Exemplo passo a passo (trabalho de pilha) para fixar a ideia: calcular \operatorname{pot}(2,3).
  • Chamada inicial: pot(2,3)
    como k=3>0, retorna 2 * pot(2,2).
  • Para pot(2,2): retorna 2 * pot(2,1).
  • Para pot(2,1): retorna 2 * pot(2,0).
  • Para pot(2,0): caso base, retorna 1.
  • Subindo na pilha: pot(2,1) = 2 * 1 = 2; pot(2,2) = 2 * 2 = 4; pot(2,3) = 2 * 4 = 8.
    Isso mostra claramente como a recursão desmonta o problema em subproblemas menores até o caso base e depois recombina os resultados.

Passo 6

Complexidade e observações finais antes do código:
  • Complexidade temporal: O(k) multiplicações (uma por nível de recursão).
  • Complexidade espacial (pilha): O(k) devido às chamadas recursivas.
  • Em provas/implementações onde k pode ser grande, existe uma versão recursiva mais eficiente (exponenciação por quadrados) com O(\log k) multiplicações — posso mostrar depois se você quiser.
  • Esta implementação simples é a mais direta e a que normalmente é pedida quando pedem “recursiva” sem otimizações.

Passo 7

Implementação em C (versão recursiva direta, com verificação de expoente negativo e comentário sobre 0^{0}):
int pot( int n, int k ) {
    /* Assumimos k >= 0. Se k < 0, o resultado seria fracionário e não cabe em int. */
    if (k < 0) {
        /* Não suportado nesta versão: retorna 0 como sinal de erro. */
        return 0;
    }
    /* Caso base: qualquer n^0 = 1 (seguimos a convenção n=0 => 0^0 = 1 aqui) */
    if (k == 0) {
        return 1;
    }
    /* Passo recursivo: n^k = n * n^(k-1) */
    return n * pot(n, k - 1);
}

Resposta

int pot( int n, int k ) {
    /* Assumimos k >= 0. Se k < 0, o resultado seria fracionário e não cabe em int. */
    if (k < 0) {
        /* Não suportado nesta versão: retorna 0 como sinal de erro. */
        return 0;
    }
    /* Caso base: qualquer n^0 = 1 (seguimos a convenção n=0 => 0^0 = 1 aqui) */
    if (k == 0) {
        return 1;
    }
    /* Passo recursivo: n^k = n * n^(k-1) */
    return n * pot(n, k - 1);
}

Exercícios relacionados