def power(a, n):
    # Base cases
    if n == 0:
        return 1
    if n == 1:
        return a

    # Recursive case: n is even
    if n % 2 == 0:
        temp = power(a, n/2)
        return temp * temp

    # Recursive case: n is odd
    if n % 2 == 1:
        temp = power(a, n/2)
        return a * temp * temp