递归

前言

在计算机编程中，递归函数是指一个函数在其定义中调用自身。例如：

func recurse() {
  // 代码
  recurse()
}

在这里，recurse() 函数在其函数体内调用了自身，因此它是一个递归函数，这种技术称为递归。了解递归之前，需要先了解 Go 函数的基本概念。

作用

递归是一种解决问题的方法，它通过函数调用自身来实现。这种方法特别适合处理分解为相似子问题的复杂问题。递归可以简化代码，减少重复的逻辑，并使得一些问题的解决方案更加直观。

使用场景

1. 计算数学问题：如计算阶乘、斐波那契数列等。
2. 处理树形结构：如文件系统遍历、解析 XML 或 JSON 数据等。
3. 解决分治问题：如排序算法（快速排序、归并排序）等。

示例

示例 1：基本递归

package main
import "fmt"

func countDown(number int) {
  // 显示数字
  fmt.Println(number)

  // 递归调用，减少数字
  countDown(number - 1)
}

func main() {
  countDown(3)
}

输出

Countdown Starts:
3
2
1
0
-1
...
...

在上述示例中，我们创建了一个名为 countDown 的函数。注意到我们在函数内部进行了递归调用：

countDown(number - 1)

这个递归函数会无限执行，因为没有停止条件。为了避免无限递归，我们需要使用条件语句来控制递归的结束。

示例 2：带条件的递归

package main
import "fmt"

// 使用 if...else 语句结束递归
func countDown(number int) {
  if number > 0 {
    fmt.Println(number)
    // 递归调用
    countDown(number - 1)
  } else {
    // 结束递归
    fmt.Println("Countdown Stops")
  }
}

func main() {
  countDown(3)
}

输出

Countdown Starts:
3
2
1
Countdown Stops

在这个示例中，我们使用了 if 语句来控制递归的停止条件：

if number > 0 {
  fmt.Println(number)
  countDown(number - 1)
} else {
  fmt.Println("Countdown Stops")
}

当 number 不大于 0 时，递归结束。这称为停止条件。

示例 3：计算正整数和的递归

package main
import "fmt"

func sum(number int) int {
  // 递归结束条件
  if number == 0 {
    return 0
  } else {
    return number + sum(number - 1)
  }
}

func main() {
  var num = 50

  // 函数调用
  var result = sum(num)

  fmt.Println("Sum:", result)
}

输出

Sum: 1275

在这个示例中，我们创建了一个名为 sum 的递归函数。如果 number 不等于 0，函数会递归调用自身并将当前值加到递归结果中。每次调用都会将 number 减少 1，直到 number 变为 0，此时递归结束。

示例 4：计算阶乘的递归

package main
import "fmt"

func factorial(num int) int {
  // 递归结束条件
  if num == 0 {
    return 1
  } else {
    // 递归调用
    return num * factorial(num - 1)
  }
}

func main() {
  var number = 3

  // 函数调用
  var result = factorial(number)

  fmt.Println("The factorial of 3 is", result)
}

输出

The factorial of 3 is 6

在这个示例中，我们创建了一个名为 factorial 的递归函数。函数每次调用自身时，将 num 减少 1，直到 num 等于 0，此时递归结束。

结语

递归是一种强大的编程技术，但也需要谨慎使用。确保在递归中包含适当的停止条件，以避免无限递归的问题。通过合理使用递归，可以简化问题的解决过程并使代码更具可读性。