SYSTEM
递归
src/content/notes/system/递归.md 递归
概述
算法:解题方案的准确而完整的描述,是一系列解决问题的清晰指令,代表着用系统的方法解决问题的策略机制
递归:程序调用自身的编程技巧
递归:
- 直接递归:自己的方法调用自己
- 间接递归:自己的方法调用别的方法,别的方法又调用自己
递归如果控制的不恰当,会形成递归的死循环,从而导致栈内存溢出错误
参考书籍:https://book.douban.com/subject/35263893/
算法
核心思想
递归的三要素(理论):
- 递归的终结点
- 递归的公式
- 递归的方向:必须走向终结点
// f(x)=f(x-1)+1; f(1)=1; f(10)=?
// 1.递归的终结点: f(1) = 1
// 2.递归的公式:f(x) = f(x - 1) + 1
// 3.递归的方向:必须走向终结点
public static int f(int x){
if(x == 1){
return 1;
}else{
return f(x-1) + 1;
}
}
公式转换
// 已知: f(x) = f(x + 1) + 2, f(1) = 1。求:f(10) = ?
// 公式转换
// f(x-1)=f(x-1+1)+2 => f(x)=f(x-1)+2
//(1)递归的公式: f(n) = f(n-1)- 2 ;
//(2)递归的终结点: f(1) = 1
//(3)递归的方向:必须走向终结点。
public static int f(int n){
if(n == 1){
return 1;
}else{
return f(n-1) - 2;
}
}
注意事项
以上理论只能针对于规律化递归,如果是非规律化是不能套用以上公式的! 非规律化递归的问题:文件搜索,啤酒问题。
应用
猴子吃桃
猴子第一天摘了若干个桃子,当即吃了一半,觉得好不过瘾,然后又多吃了一个。第二天又吃了前一天剩下的一半,觉得好不过瘾,然后又多吃了一个。以后每天都是如此。等到第十天再吃的时候发现只有1个桃子,问猴子第一天总共摘了多少个桃子?
/*
(1)公式: f(x+1)=f(x)-f(x)/2-1; ==> 2f(x+1) = f(x) - 2 ==> f(x)=2f(x+1)+2
(2)终结点:f(10) = 1
(3)递归的方向:走向了终结点
*/
public static int f(int x){
if(x == 10){
return 1;
} else {
return 2*f(x+1)+2
}
}
递归求和
//(1)递归的终点接:f(1) = 1
//(2)递归的公式: f(n) = f(n-1) + n
//(3)递归的方向必须走向终结点:
public static int f(int n){
if(n == 1 ) return 1;
return f(n-1) + n;
}
汉诺塔
public class Hanoi {
public static void main(String[] args) {
hanoi('X', 'Y', 'Z', 3);
}
// 将n个块分治的从x移动到z,y为辅助柱
private static void hanoi(char x, char y, char z, int n) {
if (n == 1) {
System.out.println(x + "→" + z); // 直接将x的块移动到z
} else {
hanoi(x, z, y, n - 1); // 分治处理n-1个块,先将n-1个块借助z移到y
System.out.println(x + "→" + z); // 然后将x最下面的块(最大的)移动到z
hanoi(y, x, z, n - 1); // 最后将n-1个块从y移动到z,x为辅助柱
}
}
}
时间复杂度 O(2^n)
啤酒问题
非规律化递归问题,啤酒 2 元 1 瓶,4 个盖子可以换 1 瓶,2 个空瓶可以换 1 瓶
public class BeerDemo{
// 定义一个静态变量存储可以喝酒的总数
public static int totalNum;
public static int lastBottleNum;
public static int lastCoverNum;
public static void main(String[] args) {
buyBeer(10);
System.out.println("总数:"+totalNum);
System.out.println("剩余盖子:"+ lastCoverNum);
System.out.println("剩余瓶子:"+ lastBottleNum);
}
public static void buyBeer(int money){
int number = money / 2;
totalNum += number;
// 算出当前剩余的全部盖子和瓶子数,换算成金额继续购买。
int currentBottleNum = lastBottleNum + number ;
int currentCoverNum = lastCoverNum + number ;
// 把他们换算成金额
int totalMoney = 0 ;
totalMoney += (currentBottleNum/2)*2; // 除2代表可以换几个瓶子,乘2代表换算成钱,秒!
lastBottleNum = currentBottleNum % 2 ;// 取余//算出剩余的瓶子
totalMoney += (currentCoverNum / 4) * 2;
lastCoverNum = currentCoverNum % 4 ;
// 继续拿钱买酒
if(totalMoney >= 2){
buyBeer(totalMoney);
}
}
}