c - 递归到迭代 - Scheme to C

Question

谁能帮我转换这个方案函数:

#lang racket
(define (powmod2 x e m)    
  (define xsqrm (remainder (* x x) m))    
  (cond [(= e 0) 1]    
        [(even? e) (powmod2 xsqrm (/ e 2) m)]    
        [(odd? e) (remainder (* x (powmod2 xsqrm (/ (sub1 e) 2) m)) m)]))

在 C 中的函数中，不要使用递归，即使用迭代。

我没有想法'，困扰我的部分是当 e 是奇数时递归调用在余数函数中。我不知道如何在 while 循环中传输它？任何提示或建议:

这是我目前所拥有的:

int powmod2(int x, int e, int m) {
    int i = x;
    int xsqrm = ((x * x) % m);
    while (e != 0){
        if (e%2 == 0) {
            x = xsqrm;
            e = (e/2);
            xsqrm = ((x * x) % m);
        }
        else {
            i = x; 
            x = xsqrm;
            e = (e - 1)/2;
            xsqrm = ((x * x) % m); 

        }
    }
    e = 1;
    return (i*e)%m;

}

Answer 1

even 版本很简单，因为代码是尾递归编写的，所以对 (powmod2 xsqrm (/e 2) m) 的调用可以通过将 e 替换为 e 和 x 的一半来迭代表示其平方模 m:

int powmod2(int x, int e, int m) { /* version for when e is a power of 2 */
  while ((e /= 2) != 0)
    x = (x * x) % m;
  return x;
}

但是奇数版本还没有写成tail递归。一种方法是创建一个使用累加器的辅助方法。然后可以针对偶数和奇数指数递归地编写此辅助方法。然后，您可以将其转换为迭代。