程序调用自身的编程技巧称为递归( recursion)。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
理论上,递归三要素可分为:
- 递归的终结点;
- 递归的公式;
-
示例1:累加求和
/**
* 求 1 - n 的和
*/
public static int f(int n){
if(n == 1 ) {
return 1;
}
return f(n - 1) + n;
}
递归的终结点:f(1) = 1;
- 递归的公式:f(n) = f(n-1) + n;
- 递归的方向走向终结点 f(1);
公式的转换
对于公式 f(x) = f(x + 1) + 2 来说,其递归的方向为正无穷,当他的终结点为 f(1) 时,就需要转换公式来解决。
即:令 x = x - 1; 则 f(x) = f(x - 1) - 2;
示例2:n 的阶乘
public static int f(int n){
if(n == 1){
return 1 ;
}else{
return f(n - 1) * n;
}
}
- 递归的终结点:f(1) = 1;
- 递归的公式
- n!= 123456…(n-1)n
f(n) = 123456…(n-1)n
f(n) = f(n-1)*n
- n!= 123456…(n-1)n
-
示例3:非规律化递归:啤酒问题
啤酒2元1瓶,4个盖子可以换一瓶,2个空瓶可以换一瓶,问10元可以喝多少瓶,剩余多少盖子和瓶子 (15 3 1)/**
* 啤酒2元1瓶,4个盖子可以换一瓶,2个空瓶可以换一瓶
* @param money 多少钱
* @param count 喝了多少瓶
* @param gaizi 剩余盖子数
* @param pingzi 剩余瓶子数
* @return
*/
public static int[] canDrink(int money,int count, int gaizi, int pingzi) {
if (money > 1 || gaizi >= 4 || pingzi >= 2) {
if (money > 0 && money != 1) {
return canDrink(money - 2, ++count, ++gaizi, ++pingzi);
}
if (gaizi >= 4) {
gaizi = gaizi - 4 + 1;
return canDrink(money, ++count, gaizi, ++pingzi);
}
if (pingzi >= 2) {
pingzi = pingzi - 2 + 1;
return canDrink(money, ++count, ++gaizi, pingzi);
}
}
return new int[]{count, gaizi, pingzi};
}
解法2:
// 定义一个静态变量存储可以喝酒的总数
public static int totalNum;
public static int lastPingZiNum;
public static int lastGaiZiNum;
public static void buyBeer(int money){
// a.拿钱买酒
int number = money / 2 ;
// 累加起来
totalNum += number;
// 算出当前剩余的全部盖子和瓶子数,换算成金额继续购买。
int currentPingZiNum = lastPingZiNum + number ;
int currentGaiZiNum = lastGaiZiNum + number ;
// 把他们换算成金额
int totalMoney = 0 ;
totalMoney +=(currentPingZiNum/2)*2;
//算出剩余的瓶子
lastPingZiNum = currentPingZiNum % 2 ;
// 换算盖子
totalMoney+=(currentGaiZiNum / 4) * 2;
lastGaiZiNum = currentGaiZiNum % 4 ;
// 继续拿钱买酒
if(totalMoney >= 2){
buyBeer(totalMoney);
}
}