반복 제곱 (파이썬)

Question

나는

(x,n)=(input(),input()) 

    def exp_itr(x,n): 
     r=1 
     while n!=0: 
      if n%2==1: 
      r=r*x 
      n=n-1 
      x=x*x 
      n=n/2 
    return r 

파이썬

의 exponentiation by squaring algorithm을 구현 그리고 지금, 나는 재귀 알고리즘을 필요로한다. 내가 어떻게 해?

Answer 1

여기에 의견

def exp(x, n): 
    if n < 0: 
     return exp(1/x, -n) 
    elif n == 0: 
     return 1 
    elif n == 1: 
     return x 
    elif n % 2 == 0: 
     return exp(x * x, n/2) 
    else: 
     return x * exp(x * x, (n - 1)/2)