递归的概念

简单的说：递归就是函数/方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

递归的三大要素

  1. 明确你这个函数想要干什么
  2. 寻找递归结束条件
  3. 找出函数的等价关系式

image.png
image.png

代码

  1. // 递归
  3. package main
  5. import "fmt"
  7. func test(n int) {
  8.     if n > 2 {
  9.         n--
  10.         test(n)
  11.     }
  12.     fmt.Println("test n = ", n)
  13. }
  15. func test02(n int) {
  16.     if n > 2 {
  17.         n--
  18.         test02(n)
  19.     } else {
  20.         fmt.Println("test02 n = ", n)
  21.     }
  22. }
  24. func main() {
  25.     test(4)
  26.     test02(4)
  27. }
  29. /*
  30. test n =  2
  31. test n =  2
  32. test n =  3
  33. test02 n =  2
  34. */

递归需要遵守的重要原则

  1. 执行一个函数时，就创建一个新的受保护的独立空间（新函数栈）
  2. 函数的局部变量是独立的，不会相互影响。如果希望各个函数栈使用同一个数据，则使用引用传递。
  3. 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了:)
  4. 当一个函数执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁

    应用场景

  • 排序
  • 二分查找
  • 阶乘
  • 斐波那契数列
  • 猴子吃桃（每一天吃当天桃子数量的一半多1个）
  • 8皇后问题
  • 汉诺塔（移动圆饼，小的在上，大的在下）
  • 迷宫问题
  • 球和篮子
  • …
  1. // 函数递归调用 + 应用场景
  2. package main
  4. import "fmt"
  6. func test(n int) {
  7.     if n > 2 {
  8.         n--
  9.         test(n)
  10.     }
  11.     fmt.Println("n = ", n)
  12. }
  14. func test2(n int) {
  15.     if n > 2 {
  16.         n--
  17.         test2(n)
  18.     } else {
  19.         fmt.Println("n = ", n)
  20.     }
  21. }
  23. // 斐波那契数
  24. func fbn(n int) int {
  25.     if n == 1 || n == 2 {
  26.         return 1
  27.     } else {
  28.         return fbn(n-2) + fbn(n-1)
  29.     }
  30. }
  32. // 猴子吃桃子
  33. // 每一天吃当天桃子数量的一半多1个，第十天的时候发现只剩下一个
  34. // 求第一天的桃子数量
  35. func peach(n int) int {
  36.     if n > 10 || n < 1 {
  37.         fmt.Println("您输入的天数不对")
  38.         return 0
  39.     }
  40.     if n == 10 {
  41.         return 1
  42.     } else {
  43.         return (peach(n+1) + 1) * 2
  44.     }
  45. }
  47. func main() {
  48.     test(4)
  49.     // test2(4)
  51.     // 斐波那契数列
  52.     // 1 ，1 ，2 ，3 ，5 ，8， 13 ，21 ，......
  53.     // f(n) = f(n-2) + f(n-1)
  54.     fmt.Println("value=", fbn(5)) // 第5个斐波那契数
  55.     // fmt.Println("value=", fbn(6)) // 第6个斐波那契数
  56.     // fmt.Println("value=", fbn(7))
  57.     // fmt.Println("value=", fbn(8))
  59.     fmt.Println("第1天的桃子数量", peach(1))
  60. }