使用递归查找两个给定数字的最大公约数的Haskell程序

---

在Haskell中，我们可以使用递归以及gcd函数和尾递归来查找两个给定数字的最大公约数。在第一个和第二个示例中，我们将使用基本情况（gcd a 0 = a）和递归情况（gcd a b = gcd b (a `mod` b)），在第三个示例中，我们将使用尾递归函数。

在以下示例中，我们定义了一个gcd函数，它接受两个Int参数a和b。该函数使用模式匹配来处理两种情况：

• 如果b为0，则函数返回a，因为a和0的最大公约数是a。

• 如果b不为0，则函数递归调用自身，参数为b和a模b。

算法

• 步骤1 - 导入Prelude库以隐藏gcd函数。

• 步骤2 - 定义用户自定义的gcd函数，包含基本情况和递归情况，如下所示：

• 对于示例1和2：

gcd a 0 = a
gcd a b = gcd b (a `mod` b).

• 对于示例3：

| a < b     = gcd b a
| b == 0    = a
| otherwise = gcd b (a `mod` b).

• 步骤3 - 程序执行将从main函数开始。main()函数控制整个程序。它被写成main = do。在main函数中，我们定义了两个变量a和b，其值分别为36和63。最后，我们将gcd a b的结果打印到控制台。

• 步骤4 - 变量“a”和“b”被初始化。它们将保存需要计算最大公约数的数字。

• 步骤5 - 调用函数后，使用‘print’函数将给定两个数字的最大公约数结果打印到控制台。

示例1

在这个例子中，使用gcd函数查找两个数字a和b的最大公约数，以计算这两个数字的最大公约数。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a 0 = a
gcd a b = gcd b (a `mod` b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

输出

9

示例2

在这个例子中，使用减法和除法运算来计算最大公约数。这种方法背后的思想是利用gcd(a, b) = gcd(b, a - b * floor(a / b))这一事实，并不断从a中减去b * floor(a / b)，直到b变为0，此时a将是最大公约数。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a 0 = a
gcd a b = gcd b (a - (a `div` b) * b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

输出

9

示例3

在这个例子中，使用gcd函数的尾递归方法查找两个数字a和b的最大公约数，以计算这两个数字的最大公约数。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a b
   | a < b     = gcd b a
   | b == 0    = a
   | otherwise = gcd b (a `mod` b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

输出

9

结论

在Haskell中，gcd函数用于计算两个数字的最大公约数。实现gcd函数的方法有很多，其中最常见的一种方法是使用欧几里得算法，该算法指出两个数字a和b的最大公约数等于b和a模b的最大公约数。它也可以使用递归实现。