使用递归查找两个给定数字的最大公约数 (GCD) 的 Swift 程序

---

本教程将讨论如何编写 Swift 程序，使用递归查找两个给定数字的最大公约数。

两个数字的最大公约数 (GCD) 也称为最大公因数 (HCF)，是指这两个给定正数的公因数中最大的正数。两个数的最大公约数不能为负数或零，两个数的最小最大公约数始终为 1。例如，假设我们有两个数字：16 和 24

所以 16 的因数 = 2x2x2x2

24 的因数 = 2x2x2x3

所以，GCD(16, 24) = 2x2x2 = 8

以下是相同的演示 -

输入

假设我们的给定输入是 -

Num1 = 16
Num2 = 24

输出

期望的输出是 -

GCD = 8

欧几里得算法

为了计算两个数的最大公约数，我们首先计算它们的因数，然后取它们共有的最大数来计算最大公约数。这种方法对于小数非常有效，但是如果数字很大，这种方法就会变得很困难。因此，为了找到小数或大数的最大公约数，我们使用欧几里得算法。在这个算法中，我们除以两个数字，直到余数变为 0。

GCD(x, y) = GCD(y, x%y)

这里，x%y 用于查找余数。

为了计算两个数字的最大公约数，我们可以使用递归方法。递归方法是一种函数调用自身以完成指定任务的方法。

算法

以下是算法 -

步骤 1 - 创建一个递归函数。

步骤 2 - 声明一个名为“output”的变量来存储余数。

let output: Int = n1 % n2

步骤 3 - 检查 output != 0。如果条件为真，则递归调用 findRecursiveGCD() 函数。否则返回 n2，因为余数为零，这意味着我们找到了两个数的最大公约数。

步骤 4 - 调用函数并将结果存储到变量中。

步骤 5 - 打印输出。

示例 1

以下程序演示了如何使用递归计算两个给定数字的最大公约数。

import Swift
import Foundation
// Recursive function to find gcd of two numbers
func findRecursiveGCD(n1: Int, n2: Int) -> Int {
   let output: Int = n1 % n2
   // Base condition
   if output != 0{
      // Calling function itself
      return findRecursiveGCD(n1: n2, n2: output)
   } else{
      return n2
   }
}
// Calling Function
var result = findRecursiveGCD(n1:27, n2:21)
print("GCD of 27 and 21 is ", result)

输出

GCD of 27 and 21 is  3

在上面的代码中，我们创建了一个名为 findRecursiveGCD 的递归函数来计算两个数的最大公约数。它使用欧几里得算法。在这个函数中，我们通过递归调用函数来找到两个数的余数。所以 findRecursiveGCD() 的工作原理是 -

findRecursiveGCD(27, 21) -

Output = 27 % 21 = 6

if 6 != 0{
   return findRecursiveGCD(n1: 21, n2: 6)
} else{
   return n2
}

Output = 21 % 6 = 3

if 3 != 0{
   return findRecursiveGCD(n1: 6, n2: 3)
} else{
   return n2
}

Output = 6 % 3 = 0

if 0 != 0{
   return findRecursiveGCD(n1: 6, n2: 3)
} else{
   return n2 = 3
}

所以 27 和 21 的最大公约数是 3。