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$x, start superscript, n, end superscript, onde $x$x é qualquer número real e $n$n é qualquer número inteiro. É fácil se $n$n é 0, já que $x^0 = 1$x, start superscript, 0, end superscript, equals, 1 não importa o que $x$x seja. Esse é um bom caso de base.

Então agora vamos ver o que aconte quando $n$n é positivo. Vamos começar falando que quando você multiplica as potências de $x$x, você soma os expoentes: $x^a \cdot x^b = x^{a+b}$x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript para qualquer base de $x$x e qualquer expoente de $a$a e $b$b. Portanto, se $n$n é positivo e par, então $x^n = x^{n/2} \cdot x^{n/2}$x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Se você tivesse que calcular $y = x^{n/2}$y, equals, x, start superscript, n, slash, 2, end superscript recursivamente, então você poderia calcular $x^n$x, start superscript, n, end superscript as $y \cdot y$y, dot, y. E se $n$n for positivo e ímpar? Então $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, e $n-1$n, minus, 1 ou é 0 ou é positivo e par. Nós acabamos de ver como calcularpotências de $x$x quando o expoente for 0 ou for positivo e par. Portanto, você poderia calcular $x^{n-1}$x, start superscript, n, minus, 1, end superscript recusivamente, e então usar esse resultado para calcular $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.

E quando $n$n for negativo? Então $x^n = 1 / x^{-n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript e o expoente $-n$minus, n é positivo uma vez que ele é negação de um número negativo. Então você pode calcular $x^{-n}$x, start superscript, minus, n, end superscript recursivamente e tomar a sua recíproca.

Colocamndo essas observações juntas, nós temos os seguintes algoritmos de calculos recursivos $x^n$x, start superscript, n, end superscript:

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.