数据结构与算法-递归
- 2020 年 4 月 6 日
- 筆記
1.什么是递归
举一个例子：大学军训的时候，一个队伍，开头的人A想知道这个队伍一共有多少人，但是每个人只能通过旁边的交流，那如何统计呢？
我们可以先找出最后一个人，A可以问旁边的人B是否为最后一个人，B又问下一个人，如此类推，等到了最后一个人，再将号码返回到第一个人A，每往前一个，号码上就+1，第一个人A就知道这个队伍有多少人了。
公式：g(n)=g(n-1)+1;g(1)=1
int AskNumberOfTeams(int n) { if(n == 1) { return 1; } return 1 + AskNumberOfTeams(n-1); }
递归可以看成一个嵌套的形式，一层层嵌套，执行相同的内容，到终止条件后往上返回结果。
递归有三个要素：1.判断问题能否才分成小问题；2.每个小问题解决方案是否一致；3.是否有终止条件
2.简单应用
斐波拉契数列
斐波拉契数列指的是1、1、2、3、5、8、13、21、34、55……。我们根据数列可以推导出，当前n位置的数值可以从前两个数值和得到，公式为f(n)=f(n-1)+f(n-2)，f(1)=1与f(2)=1这两个是递归的终止条件。
int CalFibonacci(int n) { if(n == 1 || n == 2) { return 1; } return CalFibonacci(n-1) + CalFibonacci(n - 2); }
阶乘
阶乘n!是小于等于n的正整数的积，并且0!=1，n!=1*2*3*4*……*(n-2)*(n-1)*n。根据公式可以拆分成n!=(n-1)!*n，且终止条件为0!=1。
int CalFactorial(int n) { if(n == 0) { return 1; } return CalFactorial(n - 1) * n; }
3.递归写成非递归的形式
递归的形式都是可以写成非递归的形式，用循环来替代递归。以上上面两个应用可以改写成：
斐波拉契数列
int CalFibonacciCycle(int n) { if(n == 1 || n == 2) { return 1; } int SecondValue = 1;//f(n-2) int FirstValue = 1;//f(n-1) int resultvalue;//f(n) for(int i=3; i<=n; i++) { resultvalue = FirstValue + SecondValue; SecondValue = FirstValue; FirstValue = resultvalue; } return resultvalue; }
阶乘
int CalFactorialCycle(int n) { if(n == 0) { return 1; } int FirstValue = 1;//f(n-1) int resultvalue;//f(n) for(int i=1; i<=n; i++) { resultvalue = i * FirstValue; FirstValue = resultvalue; } return resultvalue; }
