递归的三大要素

第一要素：明确你这个函数想要干什么
对于递归，我觉得很重要的一个事就是，这个函数的功能是什么，他要完成什么样的一件事

第二要素：寻找递归结束条件
所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞

第三要素：找出函数的等价关系式
第三要素就是，我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
例如，f(n) 这个范围比较大，我们可以让 f(n) = n f(n-1)。这样，范围就由 n 变成了 n-1 了，范围变小了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。
说白了，就是要找到原函数的一个等价关系式，f(n) 的等价关系式为 n f(n-1)，即
f(n) = n * f(n-1)。

**

递归的执行顺序

实例1：

  1. func run(n int){
  2.     if n >2{
  3.         n--
  4.         run(n)
  5.     }
  6.     fmt.Println(n)
  7. }
  8. func main() {
  9.     run(4)
  10. }
  11. /*
  12. 2
  13. 2
  14. 3*/
  15. 运行流程：
  16. 1.进入run方法，判断n是大于2的，执行n-=1，此时n=3，run(3)
  17. 2.n=3，执行run方法，判断n是大于2的，执行n-=1，此时n=2,run(2)
  18. 3.n=2执行run方法，判断n是小于2的，此时不会进入if，执行 fmt.Println(n)
  19. 4.执行完 fmt.Println(n),跳转调用处也就是第4行的run(n),拿到的n=2，再执行 fmt.Println(n)
  20. 5.执行完 fmt.Println(n),跳转调用处也就是第4行的run(n)，拿到的n=3，再执行 fmt.Println(n)

递归 - 图1

实例2：

func run(n int){
    if n >2{
        n--
        run(n)
    }else {
        fmt.Println(n)
    }
}
func main() {
    run(4)
}
运行流程：
1.进入run方法，判断n是大于2的，执行n-=1，此时n=3，run(3)
2.n=3，执行run方法，判断n是大于2的，执行n-=1，此时n=2,run(2)
3.n=2执行run方法，判断n是小于2的，此时不会进入if，进入 else执行 fmt.Println(i)
4.执行完3后,跳转到调用处，此时n=2,由于此时fmt.Println(i)在else里，if与else只会执行一个，所有不执行
5.接着的不执行，跳转调用处也就是第4行的run(n)，此时n=3,由于此时 fmt.Println(i)在else里，所有不执行

斐波那契队列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34…，即第一项 f(1) = 1,
第二项 f(2) = 1…,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

第一要数：求第 n 项的值
第二要素：结束条件，当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) = f(2) = 1
第三要素：找出等价的关系式，显然f(n)=f(n-1)+f(n-2)

func fbn(i int) int{
    if i==1 || i==2{
        return 1
    }else {
        return fbn(i-1)+fbn(i-2)
    }
}
func main() {
    for i:=1;i<=10;i++{
        fmt.Print(fbn(i))
    }
}
1 1 2 3 5 8 13 21 34 55

小青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

第一要数：求第 n 级台阶，总共有多少种跳法
第二要素：结束条件
求递归结束的条件，你直接把 n 压缩到很小很小就行了，因为 n 越小，我们就越容易直观着算出 f(n) 的多少，所以当 n = 1时，你知道 f(1) 为多少吧？够直观吧？即 f(1) = 1
第三要素：找出等价的关系式
每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。
第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等价关系式就求出来了。于是写出代码：

func f(n int) int {
    if n == 1{
        return 1
    }
    return f(n-1)+f(n-2)
}

显然上面的代码是不对的，当 n = 2 时，显然会有 f(2) = f(1) + f(0)，f(0)肯定是不对的，按道理是递归结束，不用继续往下调用的，但我们上面的代码逻辑中，会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用，进入死循环，正确的结束条件如下：

func f(n int) int {
    if n <= 1{
        return n
    }
    return f(n-1)+f(n-2)
}

猴子吃桃子

func num(i int) int {
    if i==10{
        return 1
    }else{
        return  (num(i+1)+1)*2
    }
}
func main()  {
    for i:=1;i<=10;i++{
        fmt.Printf("第%v天的桃子数为%v\n",i,num(i))
    }
}
第1天的桃子数为1534
第2天的桃子数为766
第3天的桃子数为382
第4天的桃子数为190
第5天的桃子数为94
第6天的桃子数为46
第7天的桃子数为22
第8天的桃子数为10
第9天的桃子数为4
第10天的桃子数为1