如何在Golang中用递归法找到两个给定数的GCD

在本教程中，我们将看到如何使用Golang语言用递归的方式找到两个数的最大公除数。我们将看到两种方法来寻找两个数字的GCD递归。第一种方法将花费更多的时间，我们将两个数字的最小值减少1，然后检查这两个数字是否都能被最小值所除。第二种方法花费的时间较少，我们用大数减去小数，直到两个数字相等。

算法

• 第1步 （- 声明变量以存储两个数字和答案。

• 第2步 （- Initializing variables）。

• 第3步 （- 调用函数来寻找GCD，用最小的数字来减少每个函数的调用，用两个数字做mod，如果mod为零则返回。

• 第4步 （- Printing the result）。

方法1：使用递归函数的非效率方法。

在这个例子中，我们将两个数字的最小值减少1，然后检查这两个数字是否能被最小值除以。

示例

package main

// fmt package provides the function to print anything
import (
   "fmt"
)

// this function finds the GCD of two numbers with three parameters
// of int type and have a return type of int type
func gcdOfTwoNumbers(number1, number2, minNumber int) int {

   // checking if the number minNumber can be divided by both number1, and number2
   if minNumber == 1 || (number1%minNumber == 0 && number2%minNumber == 0) {
      return minNumber
   }

   // returning the GCD
   return gcdOfTwoNumbers(number1, number2, minNumber-1)
}
func main() {

   // declaring the variable to store the value of two numbers
   // and a variable to store an answer
   var number1, number2, answer, minNumber int

   // initializing both the variables
   number1 = 20
   number2 = 15
   fmt.Println("Program to find the GCD of two numbers using the recursion function.")
   if number1 < number2 {
      minNumber = number1
   } else {
      minNumber = number2
   }

   // calling a function to find the GCD of two number
   // and passing a minimum of number1 and number2
   answer = gcdOfTwoNumbers(number1, number2, minNumber)

   // printing the result
   fmt.Println("The GCD of", number1, "and", number2, "is", answer)
}

输出

Program to find the GCD of two numbers using the recursion function.
The GCD of 20 and 15 is 5

方法2：使用递归函数的高效方法

在这个例子中，我们将用较小的数字减去较大的数字，直到两个数字相等，从而减少时间。

示例

package main

// fmt package provides the function to print anything
import (
   "fmt"
)

// this function finds the GCD of two numbers with two parameters
// of int type and have a return type of int type
func gcdOfTwoNumbers(number1, number2 int) int {

   // returning if both the numbers become equal
   if number1 == number2 {
      return number1
   }

   // reducing the lesser one with the greater one
   if number1 > number2 {
      number1 -= number2
   } else {
      number2 -= number1
   }

   // calling the function
   return gcdOfTwoNumbers(number1, number2)
}
func main() {

   // declaring the variable to store the value of two numbers
   // and a variable to store an answer
   var number1, number2, answer int

   // initializing both the variables
   number1 = 20
   number2 = 15
   fmt.Println("Program to find the GCD of two numbers in efficient way using the recursion function.")

   // calling a function to find the GCD of two number
   answer = gcdOfTwoNumbers(number1, number2)

   // printing the result
   fmt.Println("The GCD of", number1, "and", number2, "is", answer)
}

输出

Program to find the GCD of two numbers in an efficient way using the recursion function.
The GCD of 20 and 15 is 5

结论

这些是利用递归找到两个数字的GCD的不同方法。第二种方法比第一种方法更有效。要了解更多关于Go的信息，你可以探索这些教程。