Conteúdo principal
Curso: Computer science theory > Unidade 1
Lição 6: Algoritmos recursivos- Recursividade
- A função fatorial
- Desafio: Fatorial iterativo
- Fatorial recursivo
- Desafio: Fatorial recursivo
- Propriedades de algoritmos recursivos
- Usando recursividade para determinar se uma palavra é um palíndromo
- Desafio: A string é um palíndromo?
- Calculando a potência de um número
- Desafio: Potência recursiva
- Recursão múltipla com o triângulo de Sierpinski
- Melhorando a eficiência das funções recursivas
- Projeto: Arte recursiva
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
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 , onde é qualquer número real e é qualquer número inteiro. É fácil se é 0, já que não importa o que seja. Esse é um bom caso de base.
Então agora vamos ver o que aconte quando é positivo. Vamos começar falando que quando você multiplica as potências de , você soma os expoentes: para qualquer base de e qualquer expoente de e . Portanto, se é positivo e par, então . Se você tivesse que calcular recursivamente, então você poderia calcular as . E se for positivo e ímpar? Então , e ou é 0 ou é positivo e par. Nós acabamos de ver como calcularpotências de quando o expoente for 0 ou for positivo e par. Portanto, você poderia calcular recusivamente, e então usar esse resultado para calcular .
E quando for negativo? Então e o expoente é positivo uma vez que ele é negação de um número negativo. Então você pode calcular recursivamente e tomar a sua recíproca.
Colocamndo essas observações juntas, nós temos os seguintes algoritmos de calculos recursivos :
- O caso base é quando
, e . - Se
é positivo e par, calcule recursivamente , e então . Note que você pode conseguir utilizar apenas uma chamada recursiva nesse caso, calculando apenas uma vez, e então você multiplica o resultado dessa chamada recursiva por ele mesmo. - Se
é positivo e ímpar, calcule recusivamente , até que o expoente seja 0 ou positivo e par. Então, . - se
for negativo, calcule recursivamente , até que o expoente se torne positivo. Então, .
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?
- 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);
}
}(1 voto)