概念

• 如果在函数中存在着调用函数本身的情况，这种现象就叫递归

• 动画演示：https://visualgo.net/zh/recursion

• demo

  import "fmt"
  
  // 递归乘以n-1
  func f(n int) int {
  	if n == 1 {
  		return 1
  	}
  	return n * f(n-1)
  }
  
  func main() {
  	fmt.Println(f(5))
  }
  

  ## f(5) 调用步骤
  # 5 * f(4)
  # 5 * (4 * f(3))
  # 5 * (4 * ( 3 * f(2)))
  # 5 * (4 * ( 3 * (2 * f(1))))
  # 5 * (4 * ( 3 * (2 * 1)))
  # 5 * (4 * ( 3 * 2))
  # 5 * (4 * 6)
  # 5 * 24
  # 120
  

• 特点：

  1. 一个问题可以分解成具有相同解决思路的子问题，子子问题，换句话说这些问题都能调用同一个函数
  2. 一定会存在一个终止条件

示例

1. 斐波那契数列

• code

  package main
  
  import "fmt"
  
  // 打印斐波那契数列
  func fibonacci(n int) int {
  	if n <= 1 {
  		return 1
  	}
  	return fibonacci(n-1) + fibonacci(n-2)
  }
  
  func main() {
     	for i := 0; i < 5; i++ {
  		nums := fibonacci(i)
  		fmt.Println(nums)
  	}
  }
  // 1, 1, 2, 3, 5
  

2. 最大公约数

• code

  package main
  
  import "fmt"
  
  // 最大公约数
  func gdc(a, b int) int {
  	if b == 0 {
  		return a
  	}
  	return gdc(b, a%b)
  }
  
  func main() {
  	fmt.Println(gdc(96, 38))
  }