# 极客时间 - 22 讲
# LeetCode 50 - 求 x 的 n 次方
# 1.暴力求解
# 2.分而治之
# 3.非递归算法
# 分治思想关键是将 n 递减的速度提上来，在 n 为偶数的时候，其时间复杂度是 O(logN)

# 分而治之
def myPow(x, n):
  if not n:
    return 1
  if n < 0:
    return 1 / myPow(x, -n)
  if n % 2:
    return x * myPow(x, n-1)
  return myPow(x*x, n / 2)

print("Result = " + str(myPow(2, 4)))

# 非递归算法