我們用輾轉(zhuǎn)相除法的遞歸形式：

????int f(int m,int n)

????{

????int r=m%n;

????if(r==0) return n;

????else return f(n,r);

????}

證明算法邏輯的正確性和有窮性，最終算法得到證明。

邏輯正確性涉及到兩處return語(yǔ)句。

????第一處return語(yǔ)句的正確性證明見(jiàn)圖：右欄1~8排

????第二處return語(yǔ)句的正確性證明見(jiàn)圖：右欄剩余部分

算法的有窮性證明見(jiàn)左欄。(證明的前提是存在 x∈[1,min{m,n}]∩N 是m,n的最大公因數(shù)，而輸入的m,n是自然數(shù)保證了這一前提)

PS：根據(jù)證明我們可以發(fā)現(xiàn)：對(duì)于算法來(lái)說(shuō)，m，n的大小相對(duì)關(guān)系不影響算法（即傳入?yún)?shù)時(shí)可以有m<n）

算法證明很簡(jiǎn)單，但是復(fù)雜度的推導(dǎo)具有挑戰(zhàn)性。