https://leetcode.com/problems/powx-n/

powXN.js

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */

/*
Ideas:
    1. x^y === x^(y/2) * x^(y/2)
    2. x^y === x * x^(y-1)
    3. x^-y === 1/(x^y)
    4. x^0 === 1
IMO, you can figure out 1 & 2, but you have to know 3 & 4.

Helpful bit trickey:
- x & 1 tells you if x is odd
- x >>> 1 divides x by two and forces the result to be positive
*/
var myPow = function(x, n) {
    
    const pow = (x, n) => {
        if(n === 0) return 1; // n is 0. Case 4
        if(n & 1) return x * myPow(x, n-1); // n is odd. Case 2
        const half = pow(x, n >>> 1); // n is even. Case 1
        return half * half;
    };
    
    // case 3
    return (n < 0) ? (1 / pow(x, -n)) : pow(x, n);
};