c - 谁能解释这个递归函数我不明白它是如何返回任何东西的?
问题描述
我不明白这个递归函数它是如何计算gcd的,有人可以详细解释一下这个递归函数如何返回gcd吗?
#include <stdio.h>
long gcd(long, long);
int main() {
long x, y, hcf, lcm;
printf("Enter two integers\n");
scanf("%ld%ld", &x, &y);
hcf = gcd(x, y);
lcm = (x*y)/hcf;
printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf);
printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm);
return 0;
}
long gcd(long a, long b) {
if (b == 0) {
return a;
}
else {
return gcd(b, a % b);
}
}
解决方案
您可以在此处阅读有关此算法的信息:欧几里得算法
基本上,如果
a == bq + r
除以(so )r
的余数是什么时候a
b
0 <= r < b
然后
gcd(a, b) == gcd(b, r)
请注意,这a%b
就是余数,r
。因此,您可以使用递归来计算gcd(a, b)
什么时候r == 0
,就是那个a == bq
,或者那个b
分a
。因此,b
是 的最大公约数a, b
,也是原件 的最大公约数a, b
。此时递归调用将保持b
asa
和0
as b
,因此它返回a
。
希望这个解释涵盖一切
推荐阅读
- r - r 时间序列的频率可以大于一年吗?
- python - 如何将 cv2 / Pillow-modified 图像写入磁盘?
- java - 使用 JsonView 选择性地隐藏字段
- data-structures - 在给定一阶关系的情况下合并两个堆
- javafx - 如何一键链接各种 MouseEvent?
- python - 如何仅提取 1985-2018 年运行的时间序列的 7 月(txt 文件)
- flutter - Flutter 中的 htmlspecialchars_decode(stripslashes())
- r - 列只能是数字或字母数字值 R
- python - holoviews hv.save x 标签截止(修剪)
- git - 从 git 历史记录中的提交中删除 cognito 凭据,用密码重写 master 中的提交以删除