Conteúdo principal

Calculando a potência de um número

Embora o JavaScript possua uma função pow que calcula as potências de um número, você pode escrever uma função semelhante recursivamente, e ela pode ser muito eficiente. O único problema é que o expoente tem que ser um número inteiro.

Suponha que você queira calcular

x^{n}

, onde

x

é qualquer número real e

n

é qualquer número inteiro. É fácil se

n

é 0, já que

x^{0} = 1

não importa o que

x

seja. Esse é um bom caso de base.

Então agora vamos ver o que aconte quando

n

é positivo. Vamos começar falando que quando você multiplica as potências de

x

, você soma os expoentes:

x^{a} \cdot x^{b} = x^{a + b}

para qualquer base de

x

e qualquer expoente de

a

b

. Portanto, se

n

é positivo e par, então

x^{n} = x^{n / 2} \cdot x^{n / 2}

. Se você tivesse que calcular

y = x^{n / 2}

recursivamente, então você poderia calcular

x^{n}

y \cdot y

. E se

n

for positivo e ímpar? Então

x^{n} = x^{n - 1} \cdot x

, e

n - 1

ou é 0 ou é positivo e par. Nós acabamos de ver como calcularpotências de

x

quando o expoente for 0 ou for positivo e par. Portanto, você poderia calcular

x^{n - 1}

recusivamente, e então usar esse resultado para calcular

x^{n} = x^{n - 1} \cdot x

E quando

n

for negativo? Então

x^{n} = 1 / x^{- n}

e o expoente

- n

é positivo uma vez que ele é negação de um número negativo. Então você pode calcular

x^{- n}

recursivamente e tomar a sua recíproca.

Colocamndo essas observações juntas, nós temos os seguintes algoritmos de calculos recursivos

x^{n}

O caso base é quando $n = 0$ ‍, e $x^{0} = 1$ ‍.
Se $n$ ‍ é positivo e par, calcule recursivamente $y = x^{n / 2}$ ‍, e então $x^{n} = y \cdot y$ ‍. Note que você pode conseguir utilizar apenas uma chamada recursiva nesse caso, calculando $x^{n / 2}$ ‍ apenas uma vez, e então você multiplica o resultado dessa chamada recursiva por ele mesmo.
Se $n$ ‍ é positivo e ímpar, calcule recusivamente $x^{n - 1}$ ‍, até que o expoente seja 0 ou positivo e par. Então, $x^{n} = x^{n - 1} \cdot x$ ‍.
se $n$ ‍ for negativo, calcule recursivamente $x^{- n}$ ‍, até que o expoente se torne positivo. Então, $x^{n} = 1 / x^{- n}$ ‍.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Entrar

Classificar por:

fabiooliveira2091
Publicado há há 8 meses. Link direto para a postagem “Que enroladeira, poderia ...” de fabiooliveira2091
Que enroladeira, poderia simplificar isso tudo para:

se temos que calcular uma potência de por exemplo 2^3, vai ser igual:

2 * 2^2
=> 2 * 2 * 2^1
=> 2 * 2 * 2 * 2^0
=> 2 * 2 * 2 * 1

ou seja: 2^n vai ser igual a 2 * 2^(n -1)......

e caso queira calcular potência negativa 2^-3, vai ficar

1 / 2^3 (agora refaz o passo a passo de potência positva).

código para isso tudo:
const potenciaRecursiva = function (x, n) {
if (n === 0) {
return 1;
}

if (n > 0) {
return x * potenciaRecursiva(x, n - 1);
} else {
return 1 / potenciaRecursiva(x, n * -1);
}
}
Botão para a página de cadastroBotão para a página de cadastro
(1 voto)
Resposta

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Computer science theory

Curso: Computer science theory > Unidade 1

Quer participar da conversa?