LeetCode 50. Pow(x,n)

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

単純にx * x * x ... をn回繰り返す演算を行うと計算量がO(n)になってしまうため 10^(2^31-1)のような指数が大きいケースで時間がかかりすぎてパスしない。
今回のケースは、基本的に

$$x^n = (x^{n/2})^2$$

となることを利用して、計算量をO(log n)に落とし込むことを目標とした。
10^13の場合を例にとると、半分に分解して 10^13 = 10 * (10^6)^2となり
さらに半分に分解して10^6 = (10^3)^2・・・というのをn=0になるまで繰り返す。

class Solution {
    function myPow($x, $n) {
        $res = $this->helper($x, abs($n));
        return $n < 0 ? 1 / $res : $res;
    }

    function helper($x, $n) {
        if ($n === 0) return 1;
        if ($x === 0) return 0;

        $res = $this->helper($x, (int)floor($n/2));
        $res *= $res;

        return $n % 2 ? $x * $res : $res;
    }
}