algorithm - 扩展欧几里得算法 - 是否有非递归版本？

Question

我实现了以下版本的扩展欧几里得算法:

long gcdex(const long& a, const long& b, long& x, long& y)
{
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    
    long x1, y1;
    long d = gcdex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

我不知道如何实现它的非递归版本，你能帮我吗？

Answer 1

任何递归算法都可以使用迭代和附加堆栈实现为非递归算法。但这仍然会导致某些算法的可读性大大降低，并且可能无法提高效率。

我喜欢你的算法版本 - 它简短且可读(不过也许你需要重命名一些变量)，并且它为你提供了算法的最佳复杂性。