需要歐幾里德算法的遞歸版本

Question

我有一個任務，我有歐幾里德算法，需要做一個遞歸版本。我無法真正瞭解算法的遞歸版本是什麼，所以在這裏的任何幫助將非常感激！ :)

給定的算法是：

X ← MAX 
Y ← MIN 
while (Y != 0){ 
    mod ← X mod Y 
    X ← Y 
    Y ← mod} 
GCD ← X 

Answer 1

遞歸實際上是非常相似的迭代

GCD(X,Y): 
    if Y == 0: 
    return X 
    else: 
    return GCD(Y, X mod Y) 

Answer 2

在這裏，我假設X> = Y> 0，

本質上遞歸正在用較小的X'和Y'解決問題，直到答案很明顯（這裏X'= Y和Y'= X％Y）。

歐幾里得的解決最大公約數（GCD）的遞歸版本的算法是（C版本）：

int GCD(X, Y) 
{ 
    if ((X % Y) == 0) 
    { 
     return Y; 
    } 
    else 
    { 
     return GCD(Y, X % Y); 
    } 
}