Python递归调用求最大公约数和最小公倍数
时间: 2024-06-15 19:02:19 浏览: 12
在Python中,递归调用是一种常用的算法实现技巧,特别适用于计算像最大公约数(GCD, Greatest Common Divisor)和最小公倍数(LCM, Least Common Multiple)这样的数学问题。递归函数会不断地调用自身,直到满足基本情况,从而解决整个问题。
**递归求最大公约数(GCD)**:
```python
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
# 示例
print(gcd_recursive(48, 18)) # 输出: 6
```
**递归求最小公倍数(LCM)**:
由于没有直接的公式来快速计算LCM,我们可以利用GCD的性质:两个数的乘积等于它们的最大公约数和最小公倍数的乘积。所以,LCM可以通过以下递归方式计算:
```python
def lcm_recursive(a, b):
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
return a * b // gcd(a, b)
# 示例
print(lcm_recursive(48, 18)) # 输出: 144
```
**相关问题--:**
1. 递归是如何应用于最大公约数和最小公倍数的计算中的?
2. 为什么在计算最小公倍数时需要先计算最大公约数?
3. 当a除以b的结果为0时,递归调用会如何结束?
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)