递归

程序调用自身的编程技巧称为递归（ recursion）。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
理论上，递归三要素可分为：

1. 递归的终结点；
2. 递归的公式；

3. 递归的方向必须走向终结点；

   示例1：累加求和

   /**
   * 求 1 - n 的和
   */
   public static int f(int n){
    if(n == 1 ) {
        return 1;
    }
    return f(n - 1) + n;
   }

4. 递归的终结点：f(1) = 1;

5. 递归的公式：f(n) = f(n-1) + n；
6. 递归的方向走向终结点 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;
    }
}

1. 递归的终结点：f(1) = 1;
2. 递归的公式
   1. n!= 123456…(n-1)n
      f(n) = 123456…(n-1)n
      f(n) = f(n-1)*n

3. 递归的方向走向终结点 f(1);

   示例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);
    }
   }

取模与取余

https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html https://www.jianshu.com/p/5e1a83e8be3b

取模与取余区别

• 概念上：取模是计算机术语，取余属于数学概念；
• 结果上：当同号的两个数相除，二者相同，有负数的情况下，结果不同；
• 在 Java 中，% 运算符代表取余操作。
• 计算上：
  • 取余运算在计算商值时商值向 0 方向舍入，商值靠近0原则；
  • 取模运算在计算商值时商值向负无穷方向舍入，商值小原则；

    计算步骤

    对于整型数，取余和取模的步骤是一样的
    对于整数a，b，若想求其余数和模，则有：
    整数商：c = a / b ;
    取余/取模：r = a - b * c

取余和取模的区别在于整数商的计算方式不同，取余运算的整数商参考靠近0原则，取模运算的整数商参考商值小原则。

例子

以 5 与 3 之间运算举例：

取模

取余

深入理解

在 12 模的时钟中；假设当前时针指向 6 点，而准确时间是 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