【golang】递归求最大公约数

首先是求两个数最大公约数的数学原理：

  辗转相除法， 又名欧几里德算法,是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
使用golang实现的代码如下：

package main

import "fmt"

func divisor(min,max int) (maxDivisor int){
    //用小数除大数取余
    complement := max%min
    //余数不为零，将余数作为小数，除数作为大数，递归调用自己
    if(complement != 0){
        maxDivisor = divisor(complement,min)
    }else{
        //余数为零，除数则为最大公约数
        maxDivisor = min
    }
    return
}
func main(){
    fmt.Println(divisor(20,92))
}

运行结果：

4

有疑问加站长微信联系（非本文作者）