分别用迭代方法和递归方法实现求幂
迭代方法的时间复杂度为O(n),空间复杂度为O（1）
递归方法1的时间复杂度为O(logn),空间复杂度为O（logn）
递归方法2的时间复杂度为O（n），空间复杂度为O（n）

#!/usr/bin/env python

#coding -*- utf:8 -*-

def pow_1(x, n, choice):

    if choice==0:

        return pow_1_iter(x, n, 1)

    if choice==1:

        return pow_1_rec(x, n)

#iteration

def pow_1_iter(x, counter, product):

    if counter==0:

        return product

    else:

        return pow_1_iter(x, counter-1, x*product)

#recursion1

def pow_1_rec(x, counter):

    if counter==0:

        return 1

    #偶数情况

    if(even(counter)):

        return pow_1_rec(x*x, counter//2)

    #奇数情况

    else:

        return x * pow_1_rec(x, counter-1)

        #return x * pow_1_rec(x*x, counter//2)

'''

#recursion2

def pow_2_rec(x, counter):
    if n==0:
        return 1
    else:
        return x*pow_2_rec(x,counter-1)
'''

#判断counter是否为偶数

def even(i):

    if i%2==0:

        return True

    else:

        return False

if __name__=='__main__':

    a = int(input("Please enter the x:"))

    b = int(input("Please enter the m:"))

    c = int(input("Which method do you want?(0:iteration, 1:recursion) "))

    print("result: ",pow_1(a, b, c))