[Recursive] numberPower?

[Recursive] numberPower?

n의 x 승을 구하는 가장 빠른 방법.

// n^x 구하기
// Time: O(logN) - N/2 줄여나가면서 갯수 반씩 감소하므로
// Space: O(logN) - 스택 깊이

#include <iostream>
using namespace std;

int numberPower(int n, int x) {
   // n^0 == 1
   if(x == 0) return 1;
   // n^1 == n
   if(x == 1) return n;
   // n^3 == n * n^2
   if(x % 2 == 1) return n * numberPower(n*n, x/2);
   // n^4 == n^2 * n^2
   return numberPower(n*n, x/2);
}

int main() {
    int n, x;

    cin >> n >> x;
    cout << numberPower(n, x) << endl;
    return 0;
}