Considere a função
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.
int pot( int n, int k ) {
}
Passo 1
O enunciado pede: implementar de forma recursiva a função que calcula
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 é
. - Vou assumir que
é um inteiro não negativo ( ). Se 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
: é um caso ambíguo em matemática, mas em muitas implementações de programação é conveniente definir ; 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:
- Um caso base (quando parar de recursar).
- Um passo recursivo que reduz o problema até atingir o caso base.
No nosso problema, a redução natural vem da propriedade dos expoentes:
E o caso base natural é:
Passo 3
Definindo o caso base e a condição de validade:
- Caso base: se
retornamos porque para qualquer (seguindo a convenção para ). - Validade: se
não podemos representar (fração) com retorno int. Vou detectar esse caso e devolver um valor sentinela (por exemplo0) ou você poderia optar por tratar comdoubleem outra versão. Aqui só aviso que retornarei0para 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
usamos a definição recursiva:
- Em C, traduzimos isso por
return n * pot(n, k-1);. - Atenção aos limites: se
for grande, haverá muitas chamadas recursivas (profundidade ) 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
.
- Chamada inicial:
pot(2,3)
comok=3>0, retorna2 * pot(2,2). - Para
pot(2,2): retorna2 * pot(2,1). - Para
pot(2,1): retorna2 * pot(2,0). - Para
pot(2,0): caso base, retorna1. - 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:
multiplicações (uma por nível de recursão). - Complexidade espacial (pilha):
devido às chamadas recursivas. - Em provas/implementações onde
pode ser grande, existe uma versão recursiva mais eficiente (exponenciação por quadrados) com 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
):
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);
}