Tous les défis
Moyen 2 résolus 100.0 % de réussite

Recursive Power

Compute a power recursively by halving the exponent.

Ce que vous allez apprendre

  • Diviser l'exposant par deux à chaque appel
  • Écrire des cas de base pour la récursion
  • Passer d'un temps linéaire à logarithmique

Problème

Compute base to the power exponent with recursion: x⁰ = 1, and xⁿ = (x^(n/2))² for even n or x × (x^((n−1)/2))² for odd n. This uses far fewer multiplications than a simple loop.

Implement recursive_power(base, exponent).

Input

base: The base. exponent: The exponent (zero or positive).

Output

Return base raised to exponent.

Contraintes

-10 ≤ base ≤ 10; 0 ≤ exponent ≤ 18

Exemples

Exemple 1
Entrée :
base = 3
exponent = 5

Sortie attendue :
expected = 243
Entrée :
long long base = 3;
long long exponent = 5;

Sortie attendue :
long long expected = 243;
Entrée :
long base = 3;
long exponent = 5;

Sortie attendue :
long expected = 243;

Explication

3⁵ = 3 × (3²)² = 3 × 81 = 243.

Exemple 2
Entrée :
base = 7
exponent = 0

Sortie attendue :
expected = 1
Entrée :
long long base = 7;
long long exponent = 0;

Sortie attendue :
long long expected = 1;
Entrée :
long base = 7;
long exponent = 0;

Sortie attendue :
long expected = 1;

Explication

The base case: anything to the power 0 is 1.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Utilise la parité de l’exposant pour réduire rapidement la taille du problème.

Indice 2

L’exponentiation par carrés en récursif évite les recalculs et réduit fortement le nombre de multiplications.

Indice 3

Fais attention à l’exposant zéro et au cas de base pour les petits exposants.

Complexité attendue

temps O(log exponent), espace supplémentaire O(log exponent)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 820 ms - 5/5 Voir le code
2 LMLaura Mahlow Python 829 ms - 3/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.