欧几里德算法：递归实现求最大公约数（Java代码）

【辰兮要努力】：hello你好我是辰兮，很高兴你能来阅读，昵称是希望自己能不断精进，向着优秀程序员前行！

博客来源于项目以及编程中遇到的问题总结，偶尔会有读书分享，我会陆续更新Java前端、后台、数据库、项目案例等相关知识点总结，感谢你的阅读和关注，希望我的博客能帮助到更多的人，分享获取新知，大家一起进步!

吾等采石之人，应怀大教堂之心，愿你们奔赴在各自的热爱中…

斐波那契数列和递归求N阶乘（Java递归案例）

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

/**
 * 
 * @Description:  [递归求解：欧几里德算法]
 * @Author:       辰兮
 * @CreateDate:   2021年1月18日21:00:03
 */
public class Gcd {
	
	public static int gcd(int m, int n){
		/*递归终结条件*/
		if (n == 0){
			return m;
		}
		/*递归调用*/
		return gcd(n, m%n);
	}
	public static void main(String[] args) {
		System.out.println(Gcd.gcd(6,4));
		System.out.println(Gcd.gcd(18,15));
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

运行结果

2
3

  

 

  
1
  
2
 

分析总结：
1.结束的条件，最后的余数为0
2.等价的等式：除数和余数反复做除法运算

小贴士：要知道Java中/与%的区别

/结果等于得到的整数（商的整数）

System.out.println(4/5)  = 0；
System.out.println(6/5)  = 1；

  

 

  
1
  
2
 

%代表结果等于余数（剩余多少）

System.out.println(17%5) = 2;
System.out.println(16%5) = 1;
System.out.println(2%5) = 2;

  

 

  
1
  
2
  
3
 

非常感谢你阅读到这里，如果这篇文章对你有帮助，希望能留下你的点赞👍 关注❤️ 分享👥 留言💬thanks！！！

2021.01.18 21:25 愿你们奔赴在自己的热爱里！

文章来源: blessing.blog.csdn.net，作者：辰兮要努力，版权归原作者所有，如需转载，请联系作者。

原文链接：blessing.blog.csdn.net/article/details/112794992