Рекурсия хвоста в петлю

Question

Я работаю над программой, заданной a и b, вычисляет последние 5 цифр a^b. В настоящее время я работаю до тех пор, пока b достаточно низкий, но если b велико (> 1000), это сокрушит стек. Есть ли способ сделать это итеративной функцией? Я попытался преобразовать в итеративный, но я не могу понять это.

def pow_mod(a,b): 
    if b == 0: 
     return 1 
    elif b == 2: 
     return a*a % 10000 
    return ((b%2*(a-1) + 1) * pow_mod(a,b//2)**2) % 10000 

Answer 1

Используйте while петлю вместо рекурсии, чтобы настроить b таким же образом, что вы делаете в рекурсивном вызове.

def pow_mod(a, b): 
    result = 1 
    while b > 0: 
     result = (b%2*(a-1) + 1) * result**2) % 10000 
     b = b//2 
    return result 

Answer 2

Для того, чтобы сделать это вычисление, итеративно, вы начинаете с ответом = а, а затем квадрат его повторно (и умножить на а, если б нечетно). Чтобы выйти из цикла, разделите b на 2 каждый раз и проверьте, когда b> 1.

def pow_mod(a,b): 
    if b == 0: 
     return 1 
    c = 1; 
    while b > 1: 
     if b % 2: 
      c *= a 
     a *= a 
     b //= 2 
     a %= 10000 
     c %= 10000 
    return a * c % 10000 

Answer 3

Трюк заключается в том, чтобы сохранить результат во временной переменной, а затем передать его каждому вызову функции.

lst = [] 
while b: 
    lst.insert(0, b) 
    b = b//2 

def _pow_mod(a, b, answer): 
    if b == 2: 
     return a*a % 10000; 
    else: 
     return ((b%2*(a-1) + 1) * answer **2) % 10000 

answer = 1 # b = 0 case 
for b in lst: 
    answer = _pow_mod(a, b, answer) 

Полный код:

# Original recursive solution 
def pow_mod_orig(a, b): 
    if b == 0: 
     return 1 
    elif b == 2: 
     return a*a % 10000 
    return ((b%2*(a-1) + 1) * pow_mod_orig(a,b//2)**2) % 10000 

# Iterative solution 
def pow_mod(a, b): 

    lst = [] 
    while b: 
     lst.insert(0, b) 
     b = b//2 

    def _pow_mod(a, b, answer): 
     if b == 2: 
      return a*a % 10000; 
     else: 
      return ((b%2*(a-1) + 1) * answer **2) % 10000 

    answer = 1 # b = 0 case 
    for b in lst: 
     answer = _pow_mod(a, b, answer) 

    return answer 


for i in range(1000): 
    assert(pow_mod_orig(3, i) == pow_mod(3, i))