Java二十八：递归和取模与取余
递归
程序调用自身的编程技巧称为递归（ recursion）。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
理论上，递归三要素可分为：
递归的终结点；
递归的公式；
递归的方向必须走向终结点；
引用java递归实现99乘法表
package com.example.demo.test4;
/**
* @program: test
* @description:
* @author: liulq
* @create: 2022-01-11 10:45
*/
publicclass Day {
public static void main(String args[]) {
m(9);
}
/**
* 打印出九九乘法表
* @param i
*/
public static void m(int i) {
if (i == 1) {
System.out.println("1*1=1 ");
} else {
m(i - 1);
for (int j = 1; j <= i; j++) {
System.out.print(j + "*" + i + "=" + j * i + " ");
}
System.out.println();
}
}
}
示例1：累加求和
/**
* 求 1 - n 的和
*/
public static int f(int n){
if(n == 1 ) {
return1;
}
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){
return1 ;
}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
递归的方向走向终结点 f(1);
示例3：非规律化递归：啤酒问题
啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶，问10元可以喝多少瓶，剩余多少盖子和瓶子 （15 3 1）
/**
* 啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶
* @param money 多少钱
* @param count 喝了多少瓶
* @param gaizi 剩余盖子数
* @param pingzi 剩余瓶子数
* @return
*/
publicstaticint[] 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);
}
}
returnnewint[]{count, gaizi, pingzi};
}
解法2：
// 定义一个静态变量存储可以喝酒的总数
publicstaticint totalNum;
publicstaticint lastPingZiNum;
publicstaticint 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);
}
}
取模与取余区别
概念上：取模是计算机术语，取余属于数学概念；
结果上：当同号的两个数相除，二者相同，有负数的情况下，结果不同；
在 Java 中，
%运算符代表取余操作。计算上：
取余运算在计算商值时商值向 0 方向舍入，商值靠近0原则；
取模运算在计算商值时商值向负无穷方向舍入，商值小原则；
计算步骤
对于整型数，取余和取模的步骤是一样的
对于整数a，b，若想求其余数和模，则有：
整数商：c = a / b ;
取余/取模：r = a - b * c
取余和取模的区别在于整数商的计算方式不同，取余运算的整数商参考靠近0原则，取模运算的整数商参考商值小原则。
例子
以 5 与 3 之间运算举例：
取模
简述商值计算过程取模值5 mod 3 = 25/3 = 1.66 商取小原则 商=15 - 3 * 1 = 22-5 mod 3 = 1-5/3 = -1.66 商取小原则 商=-2-5 - (3 * -2) = 115 mod -3 = -15/-3 = -1.66 商取小原则 商=-25 - (-3 * -2) = -1-1-5 mod -3 = -2-5/-3 = 1.66 商取小原则 商=1-5 - (-3 * 1) = 2-2
取余
简述商值计算过程取余值5 rem 3 = 25/3 = 1.66 商靠0原则 商=15 - 3 * 1 = 22-5 rem 3 = -2-5/3 = -1.66 商靠0原则 商=-1-5 - (3 * -1) = - 2-25 rem -3 = 25/-3 = -1.66 商靠0原则 商=-15 - (-3 * -1) = 22-5 rem -3 = -2-5/-3 = 1.66 商靠0原则 商=1-5 - (-3 * 1) = - 2-2
深入理解
在 12 模的时钟中；假设当前时针指向 6 点，而准确时间是 2 点，调整时间最少有以下两种拨法
倒拨4小时：6-4=2正拨8小时：(6+8) mod 12=2
除此之外，还有 正拨 8 +12 小时等，(6+20) mod 12 = 2；
mod 为取模，在正整数中结果等于取余数。
即上面结果表明，正拨（加法）的结果可以用倒拨（减法）来替代！
而对于如何用一个正数来替代一个负数（减法可以看到加一个负数），数学上有一个概念叫做同余。
同余
两个整数 a，b，若他们的除以整数 m 所得的余数相等，则称 a，b 对于模 m 同余。记作 a ≡ b (mod m)，读作 a 与 b 关于模 m 同余。
举例：
2 mod 12 = 2
14 mod 12 = 2
26 mod 12 = 2
所以，2、14、26 关于模 12 同余
应用
取模的本质是：取模的值，必定在模的范围内；所以，计算机领域引用该特性，使元素路由算法不超出边界，并有规则存放。
首先确定模(范围)；元素取模，使元素有规则的落入模的范围内容器中。即余数的范围小于除数的值。
举例：
对于两个整数 a，b
如果 a <= b，令 r = a % b，则 0 <= r < b，且只有当 a = b 时，r = 0；
3 % 5 = 3
2 % 5 = 2
5 % 5 = 0
参考的文章：
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
https://www.jianshu.com/p/5e1a83e8be3b
总结：
1、引用递归可以实现java的一些复杂的实现，简化代码
2、概念上：取模是计算机术语，取余属于数学概念；
结果上：当同号的两个数相除，二者相同，有负数的情况下，结果不同；
在 Java 中，
%运算符代表取余操作。计算上：
取余运算在计算商值时商值向 0 方向舍入，商值靠近0原则；
取模运算在计算商值时商值向负无穷方向舍入，商值小原则；
3、取余和取模的区别在于整数商的计算方式不同，取余运算的整数商参考靠近0原则，取模运算的整数商参考商值小原则。
4、在一些精确度的需求时会用到
