聊聊递归“肥宅快乐水”的那些事儿

欢迎关注【笙晨闲谈】微信公众号，闲谈、干货一应俱全，只要你关注，就会有故事~

PS：写 在 前 面

Hello！好像又好长时间不跟大家见面了，大家有没有想笙晨呢？（不用解释，笙晨知道你很想很想的呢~~）

最近笙晨真的是在忙着期末考试的事情，所以真的来不及更文了，在此向大家再次表示歉意（我错了，下次还敢）不过近期由于笙晨期末考试的时间有所改变，因此笙晨就首先想到了大家，在繁忙的期末复习当中来给大家更文（我才不会说是为了刷一波存在感呢~我也不会说是我不想复习了）

由于之前笙晨更的文章都是闲谈一类的，虽说大家都能忙里偷闲的找个乐子，但是毕竟笙晨这个公众号里面还有一部分是一些干货嘛。

因此今天，笙晨就想来跟大家简单的聊一聊递归里面一个比较经典的问题——喝汽水。

至于笙晨为什么说只是简单的聊一聊，毕竟递归如果想要说明白，是件非常不容易的事情，里面牵扯到的知识点太多了，最起码数据结构要提一下吧，里面的栈要详细说一下吧……（我才不会说是因为要搜集的资料太多，现在弄太费时间呢）所以，为了通俗易懂些，咱们就不扯那么多了，今天就直奔主题，“肥宅快乐水”走起~~

哦，对了，笙晨给大家来个温馨提示：在读这篇文章之前，大家可以去楼下买瓶“肥宅快乐水”，边喝边看哦~~

---

01

初识“递归”

说到“递归”，笙晨相信有很多小伙伴们还不是特别了解吧，老规矩，度娘走起——

“递归”：程序调用自身的编程技巧称为递归（recursion）。递归作为一种算法在程序设计语言中广泛应用，一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

什么？？竟然没看懂？？也正常

哈哈哈哈~~

其实在笙晨看来，“递归”这个东西啊，说白了就是人家在运行的过程中，自己调用自己的一个过程嘛，Emm……好像大概也许是这么回事儿吧~~（用那句话说叫啥来着？兜兜转转又回到了从前？？）

02

初识“肥宅快乐水”

看到这个标题，笙晨相信很多小伙伴们就会有疑惑了，“肥宅快乐水”谁还没喝过啊，这不刚刚就去楼下买了两瓶，这还需要笙晨亲自来教我们认识一下了？？

好了啦，言归正常，其实笙晨这里的初识“肥宅快乐水”是想介绍一下“递归”里面那个比较经典的“喝汽水”问题。

曾经“菊厂”貌似出过这么一道面试题：

一个人买汽水，一块钱一瓶汽水，三个瓶盖可以换一瓶汽水，两个空瓶可以换一瓶汽水，问20块钱可以买多少汽水？

看到这个题，很多小伙伴们可能会说，哎呀，这么简单的问题还是华为的面试题嘛？我小学就会做了，来张纸，分分钟给你答案——

此图有错误哦~

哎……上面这张图大家就当是看个乐子吧，请大家忽略笙晨乱画的草稿。

毕竟，笙晨……Emm……算了不找理由了，笙晨承认自己算错了，也不想再改了……期中笙晨在第一步进行完之后，统计剩余的盖子和瓶子的时候，就统计错了，导致了后面统统算错了。

经过刚刚这一番周折，笙晨真的是有点吃不消了，不愧是华为的大佬出的题啊（大佬请收下我的膝盖~~）

好吧，笙晨承认不会数数……想给大家重新写一遍，但是由于实在是太麻烦了（我绝对不会说是因为我懒）所以大家就凑付着看看吧，反正原理是这么个原理，大家就自己脑补一下下吧~~

哦，对了，给大家公布一下正确答案啊，当你有20块钱的时候，你去买“肥宅快乐水”，如果你不怕撑的话，那你应该是可以喝到113瓶哦~~

03

写不下去了，啊啊啊~~

说实话，这篇文章写到这里，笙晨真的是有点写不下去了，但是既然都开了这个头了，也要坚持写下去不是？所以还是耐着性子加油干吧！！所以下面我们就话不多说了，直接上代码吧——

import java.util.Scanner;

public class SoDaWater2 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        for(;;) {

            System.out.print("请输入你的金额：");

            //从键盘输入我的钱数

            int money = scanner.nextInt();

            // 第一次的钱能喝的汽水瓶数(一元钱一瓶汽水)

            int n = money / 1;

            // 我能喝的汽水数

            int sum = sodaWater(n, 0, 0);

            System.out.println("当我有" + money + "元时，总共能喝" + sum + "瓶饮料");

        }

    }

    /**

    * 用递归计算n元钱最多能喝多少瓶汽水

    * @param n 饮料瓶数

    * @param bottle 空瓶数

    * @param cap 瓶盖数

    * @return

    */

    private static int sodaWater(int n, int bottle, int cap) {

        // 兑换剩下的空瓶数

        bottle %= 2;

        // 喝完饮料剩下的空瓶

        bottle += n;

        // 兑换剩下的瓶盖数

        cap %= 3;

        // 喝完饮料剩下的瓶盖

        cap += n;

        if (bottle < 2 && cap < 3) { // 如果空瓶数<2 并且 瓶盖数<3, 那么停止兑换

            return n;

        }else {

            return n + sodaWater(bottle/2 + cap/3, bottle, cap);

        }

    }

}

04

换个简单点儿的呗~~

看到这里，笙晨觉得大家好像有点儿晕头转向的了吧，但是我们还是要解决问题不是？因此笙晨还找了一个比较简单点的题目，甚至我们直接用 n 来表示，好像这样就不需要像前面那样，那么大张旗鼓的动用巨大的精力去算了吧，让我们一起来看看是什么题目——

一块钱一瓶汽水，喝完之后两个空瓶换一瓶汽水。若现在你有n元钱，那你最多能喝多少瓶汽水？

貌似很多小伙伴们看到这个题目都会随手拿张打草纸开始写了吧：

经过以上分析我们可以得出，这是一个首项为1，公差为2的等差数列，也就是说：当你有n元钱时，在你不怕撑的情况下，最多能喝到（2n-1）瓶“肥宅快乐水”。

05

如果用代码如何解决呢 ？？

要想用代码来解决这个问题，我们首先要试着来分析一下这个题目（我们暂时先不考虑换不完的问题)：

当你有n元钱的时候，你买了n瓶汽水，喝完之后可以剩下n个空瓶；

然后你又用n个空瓶，换了n/2瓶汽水，喝完之后可以剩下n/2个空瓶；

然后你又用n/2个空瓶，换了(n/2)/2瓶汽水，喝完之后你又剩下了(n/2)/2个空瓶；

……

以此类推，最后你用2个空瓶，换了一瓶汽水，然后喝完汽水，剩下最后一个空瓶，因为这时你只剩下了一个空瓶了，换不了，所以就直接扔掉了。

看完上面笙晨的分析，有没有觉得这似乎是一个循环往复，周而复始的问题？

当你拿到汽水，喝掉之后，再去用空瓶换汽水，而且当最后你只有一瓶汽水的时候，兑换结束，这想不想是一个中止条件？

好啦，这个题目到这里基本上就可以算是分析完毕，接下来我们便可以开始撸代码了——

/**

    * 计算最多能喝多少瓶汽水，并返回这个值

    * @param n 表示有n瓶汽水

    * @return

    */

    private static int soda(int n) {

        if (n == 1) {

            // 递归终止条件，当还有一瓶饮料的时候只能喝一瓶,不能再换了

            return 1;

        }else if(n % 2 == 0) {

            // 偶数瓶，这时空瓶刚好能够换完

            return n + soda(n/2);

        }else {

            // 奇数瓶，这一次剩下的一个空瓶子刚好和最后一次的一个空瓶子能换一瓶饮料，所以要+1

            return n + 1 + soda(n/2);

        }

    }

至于为什么在奇数瓶的时候还要+1，大家可以自己画画图理解一下啦（我才不会说是我不想画了呢）其实通过简单的画图，我们可以发现：当有奇数瓶时，再复杂的情况，也无非就是3瓶时的叠加嘛~

因此，我们试着在main方法里面调用一下，来检验一下结果：

public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        for(;;) {

            System.out.print("请输入你的金额：");

            // 从键盘输入我的钱数

            int money = scanner.nextInt();

            // 第一次的钱能喝的汽水瓶数(一元钱一瓶汽水)

            int n = money / 1;

            // 我能喝的汽水数

            int sum = soda(n);

            System.out.println("当我有" + money + "元时，总共能喝" + sum + "瓶饮料");

        }

    }

Nice！！让我们来看一下运行结果：

但是看到这里，笙晨相信有很多小伙伴们或许就会有疑惑了：你为啥非要用递归嘞？人家循环它不香嘛？？

好，既然说了，笙晨满足你们这个愿望，我们用循环来操作一番——

/**

    * 用循环来计算最多能喝多少瓶汽水

    * @param n

    * @return

    */

    private static int soda2(int n) {

        // 总共能喝的饮料瓶数

        int sum = n;

        // 当n==1时循环结束，所以n>1

        for (; n > 1; n = n/2) {

            if (n % 2 == 0) {

                sum += n/2;

            }else {

                // 此次的饮料瓶数是奇数瓶就+1

                sum += (n/2 + 1);

            }

        }

        return sum;

    }

然后，让我们将上面main方法中，计算喝汽水的方法，直接改为这个方法：

// 我能喝的汽水数

int sum = soda2(n);

接着运行一下，你就会惊奇的发现：哇哦，他们的结果是一样的诶（这里笙晨就不再展示运行结果了，毕竟结果都是一样的嘛）

咦？等等，笙晨突然想到，我们之前不是还用推导公式来着嘛？？现在为啥不用了呢？非要挨着去分情况讨论，我还费那么多事情干啥？？（我才不会说是当时脑子短路了呢）

所以我们就可以直接用前面推导出来的（2n-1）这个公式直接来算了：

/**

    * 直接用推导出的数学公式（2n-1）来计算

    * @param n

    * @return

    */

    private static int soda3(int n) {

        return 2 * n - 1;

    }

接着调用，让我们来调用测试一下：

// 我能喝的汽水数

int sum = soda3(n);

Nice！！相信大家都运行出结果来了吧，是不是跟之前的结果都是一样的？好吧，请数学爸爸再爱我一次吧~~（请收下我的膝盖）

其实当我们在之前分情况讨论，以及用公式来敲代码的过程中，基本上也会出现一些问题，比如：

（1）当我们用分情况讨论的时候，我们会发现，其中当奇数瓶时，里面的那个+1实在是不太好理解，这也就导致了代码的可读性较差；

（2）但是如果我们改成用公式来计算的话，Emm……这办法好是好，但是你能保证你的智商一直在线？？毕竟咱有时候不会推导数学公式啊（笙晨才不会说自己笨呢，略略略）；

（3）还有一点我们就牵扯到了一丢丢的数据结构的知识了，虽说对于这个题来说，递归和循环的解法相比似乎没有什么两样，甚至我们仔细想一下，这个题如果用递归解决，甚至都不如直接用循环来的好，毕竟递归的空间复杂度要更高嘛（你又要人家入栈，又要人家出栈的，空间复杂度能不高嘛？？）

但是我们回头细思，在每次周而复始的过程中，不但有汽水这个变量，还有空瓶这个变量啊，那我们为何不试着直接引入空瓶这个变量来解决问题呢？话不多说，代码走起——

/**

    * 用递归计算出最多能喝多少瓶汽水

    * @param n 饮料瓶数

    * @param bottle 空瓶数

    * @return

    */

    private static int soda1(int n, int bottle) {

        // 兑换剩下的空瓶数

        bottle %= 2;

        // 喝完饮料剩下的空瓶数

        bottle += n;

        if (bottle < 2) { // 如果空瓶数<2，停止兑换

            return n;

        } else {

            return n + soda1(bottle/2, bottle);

        }

    }

让我们直接调用测试一下：

// 我能喝的汽水数

int sum = soda1(n, 0);

Nice！！！结果竟然也是跟之前的一样！！！这下才可以算是完美了一丢丢，这时候我们的代码可读性也比之前要强很多了吗，而如果要是用循环来控制两个变量，来解决这个问题的话，那么代码很可能又会变得非常复杂。

好了，到这里基本上笙晨能搜集到的关于这个题的一些解法基本上就是这么多了，后续也希望有小伙伴们可以跟笙晨一起讨论哦~~

---

PS：写 在 最 后

至此，笙晨今天跟大家分享的关于递归里面的“肥宅快乐水”问题，也就算是告一段落了，递归这东西说简单也简单，说难也还真的挺难的，或许后续笙晨也会专门抽出一些时间来跟大家详细的聊一聊“递归”的那些事儿，今天我们也就到此为止吧。

哦，对了，老师下课前貌似都是总结一下今天讲到的一些知识点，所以笙晨也来简单的总结一下吧，就让笙晨来简单总结一下“递归”和“循环”的区别吧：

（1）递归：其实递归就是程序调用自身的一种编程技巧。在Java中具体表现为方法在方法体内部直接或间接调用方法本身。他可以说是比较懒的啦，每次做事情都会留一些，然后再回来，反序地把这些剩下的事情一一做完。

说的简单粗暴点，就像是你妈让你去扫个地，你第一遍却没有扫干净，但是又迫于无奈，想想晚上的那口晚饭，你干脆心一横，直接用拖把反方向回来再拖一遍；

（2）循环：循环就是重复性的执行某段程序。但是人家循环跟递归还又不太一样，貌似还是个直男，直接就一次性干脆利落的把活儿全都干完了，之后便永不回头，干脆理都不理你了……

好啦，今天笙晨跟大家就分享到这里了，哦，不对还有一点，笙晨还想说一下，就是有些小伙伴们之前提到的一点：既然递归能干的事情，人家循环也能干啊，你为啥偏偏要选递归而不用循环嘞？

其实虽说递归能干的事情，循环貌似也能干，甚至好像会更简单，但是我们要知道一点：循环能解决的问题，递归一般也能解决；但是递归能解决的问题，循环就不一定能解决了。毕竟人家递归是运用的是“分而治之”的思想，把一个复杂的原问题拆分成若干个子问题来解决，这里面妙就妙在递归能用有限的语句表现出无限的过程。但是如果我们不了解递归，可能也就掌握不了快排、归并排序等算法了，这些都是些后话了，咱们以后再说。

好啦好啦，这次是真的没了，笙晨今天就跟大家聊到这里了，大家如果对递归有兴趣的话，还可以直接通过度娘等方式，去自己学习一下哦~~

我们几天，甚至是好几天后再见咯，bye~~

---

PS：原文链接：聊聊递归“肥宅快乐水”的那些事儿

看完记得关注【笙晨闲谈】微信公众号，不定期更新“计算机”类的相关干货，以及闲谈类的文章。只要你关注，就会有故事哦~