Swift 程序使用递归查找两个给定数的最大公约数 (GCD)
本教程将讨论如何编写 Swift 程序，使用递归查找两个给定数的最大公约数 (GCD)。
两个数的最大公约数 (GCD) 是指两个给定正数的共同因数中较大的一个。GCD 也称为最高公因数 (HCF)。两个数的最大公约数 (GCD) 不能为负数或零，且两个数的最小 GCD 值始终为 1。例如，假设我们有两个数:16 和 24
因此 16 的因数 = 2x2x2x2
24 的因数 = 2x2x2x3
因此，GCD(16, 24) = 2x2x2x2 = 8
以下是相同的演示 -
输入
假设给定的输入为 -
Num1 = 16 Num2 = 24
输出
期望输出为 -
GCD = 8
欧几里得算法
要计算两个数的最大公约数 (GCD)，我们首先计算它们的因数，然后取它们的最大公因数来计算 GCD。这种方法对于较小的数非常有效，但如果数很大，就比较难了。因此，为了求大数或小数的最大公约数，我们使用欧几里得算法。在这个算法中，我们将两个数相除，直到余数为 0。
GCD(x, y) = GCD(y, x%y)
这里，x%y 用于求余数。
要计算两个数的最大公约数，我们可以使用递归方法。递归方法是一种函数调用自身来完成指定任务的方法。
算法
以下是算法 -
步骤 1 - 创建一个递归函数。
步骤 2 - 声明一个名为"output"的变量来存储余数。
let output: Int = n1 % n2
步骤 3 - 检查 output 是否 != 0。如果条件成立，则递归调用 findRecursiveGCD() 函数。否则返回 n2，因为余数为零，这意味着我们找到了两个数的最大公约数 (GCD)。
步骤 4 - 调用函数并将结果存储到变量中。
步骤 5 - 打印输出。
示例 1
以下程序演示如何使用递归计算两个给定数的最大公约数 (GCD)。
import Swift
import Foundation
// 递归函数，用于查找两个数的最大公约数
func findRecursiveGCD(n1: Int, n2: Int) -> Int {
let output: Int = n1 % n2
// 基本条件
if output != 0{
// 调用函数本身
return findRecursiveGCD(n1: n2, n2: output)
} else{
return n2
}
}
// 调用函数
var result = findRecursiveGCD(n1:27, n2:21)
print("GCD of 27 and 21 is ", result)
输出
GCD of 27 and 21 is 3
在上面的代码中，我们创建了一个名为 findRecursiveGCD 的递归函数来计算两个数的最大公约数 (GCD)。它使用了欧几里得算法。在此函数中，我们通过递归调用该函数来求两个数的余数。因此，findRecursiveGCD() 的工作原理如下:-
findRecursiveGCD(27, 21) -
输出 = 27 % 21 = 6
if 6 != 0{
return findRecursiveGCD(n1: 21, n2: 6)
} else{
return n2
}
输出 = 21 % 6 = 3
if 3 != 0{
return findRecursiveGCD(n1: 6, n2: 3)
} else{
return n2
}
输出 = 6 % 3 = 0
if 0 != 0{
return findRecursiveGCD(n1: 6, n2: 3)
} else{
return n2 = 3
}
因此 27 和 21 的最大公约数是 3。
