歡迎關(guān)注【笙晨閑談】微信公眾號救赐，閑談、干貨一應(yīng)俱全切油，只要你關(guān)注蝙斜，就會有故事~
PS：寫 在 前 面
Hello！好像又好長時間不跟大家見面了澎胡，大家有沒有想笙晨呢孕荠？（不用解釋，笙晨知道你很想很想的呢~~）
最近笙晨真的是在忙著期末考試的事情攻谁，所以真的來不及更文了稚伍，在此向大家再次表示歉意（我錯了，下次還敢）不過近期由于笙晨期末考試的時間有所改變戚宦，因此笙晨就首先想到了大家个曙，在繁忙的期末復(fù)習(xí)當(dāng)中來給大家更文（我才不會說是為了刷一波存在感呢~我也不會說是我不想復(fù)習(xí)了）
由于之前笙晨更的文章都是閑談一類的，雖說大家都能忙里偷閑的找個樂子受楼，但是畢竟笙晨這個公眾號里面還有一部分是一些干貨嘛垦搬。
因此今天呼寸，笙晨就想來跟大家簡單的聊一聊遞歸里面一個比較經(jīng)典的問題——喝汽水。
至于笙晨為什么說只是簡單的聊一聊猴贰，畢竟遞歸如果想要說明白对雪，是件非常不容易的事情，里面牽扯到的知識點太多了糟趾，最起碼數(shù)據(jù)結(jié)構(gòu)要提一下吧慌植，里面的棧要詳細說一下吧……（我才不會說是因為要搜集的資料太多甚牲，現(xiàn)在弄太費時間呢）所以义郑，為了通俗易懂些，咱們就不扯那么多了丈钙，今天就直奔主題非驮，“肥宅快樂水”走起~~
哦，對了雏赦，笙晨給大家來個溫馨提示：在讀這篇文章之前劫笙，大家可以去樓下買瓶“肥宅快樂水”，邊喝邊看哦~~
01
初識“遞歸”
說到“遞歸”星岗，笙晨相信有很多小伙伴們還不是特別了解吧填大，老規(guī)矩，度娘走起——
“遞歸”：程序調(diào)用自身的編程技巧稱為遞歸（recursion）俏橘。遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用允华，一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解寥掐，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算靴寂，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合召耘。一般來說百炬，遞歸需要有邊界條件、遞歸前進段和遞歸返回段污它。當(dāng)邊界條件不滿足時剖踊，遞歸前進；當(dāng)邊界條件滿足時衫贬，遞歸返回德澈。
什么？祥山？竟然沒看懂圃验？？也正常
哈哈哈哈~~
其實在笙晨看來缝呕，“遞歸”這個東西啊澳窑，說白了就是人家在運行的過程中斧散，自己調(diào)用自己的一個過程嘛，Emm……好像大概也許是這么回事兒吧~~（用那句話說叫啥來著摊聋？兜兜轉(zhuǎn)轉(zhuǎn)又回到了從前鸡捐？？）
02
初識“肥宅快樂水”
看到這個標題麻裁，笙晨相信很多小伙伴們就會有疑惑了箍镜，“肥宅快樂水”誰還沒喝過啊，這不剛剛就去樓下買了兩瓶煎源，這還需要笙晨親自來教我們認識一下了色迂？？
好了啦手销，言歸正常歇僧，其實笙晨這里的初識“肥宅快樂水”是想介紹一下“遞歸”里面那個比較經(jīng)典的“喝汽水”問題。
曾經(jīng)“菊廠”貌似出過這么一道面試題：
一個人買汽水锋拖，一塊錢一瓶汽水诈悍，三個瓶蓋可以換一瓶汽水，兩個空瓶可以換一瓶汽水兽埃，問20塊錢可以買多少汽水侥钳？
看到這個題，很多小伙伴們可能會說柄错，哎呀舷夺，這么簡單的問題還是華為的面試題嘛？我小學(xué)就會做了鄙陡，來張紙冕房，分分鐘給你答案——
哎……上面這張圖大家就當(dāng)是看個樂子吧，請大家忽略笙晨亂畫的草稿趁矾。
畢竟耙册，笙晨……Emm……算了不找理由了，笙晨承認自己算錯了毫捣，也不想再改了……期中笙晨在第一步進行完之后详拙，統(tǒng)計剩余的蓋子和瓶子的時候，就統(tǒng)計錯了蔓同，導(dǎo)致了后面統(tǒng)統(tǒng)算錯了饶辙。
經(jīng)過剛剛這一番周折，笙晨真的是有點吃不消了斑粱，不愧是華為的大佬出的題捌俊（大佬請收下我的膝蓋~~）
好吧，笙晨承認不會數(shù)數(shù)……想給大家重新寫一遍，但是由于實在是太麻煩了（我絕對不會說是因為我懶）所以大家就湊付著看看吧矿微，反正原理是這么個原理痕慢，大家就自己腦補一下下吧~~
哦，對了涌矢，給大家公布一下正確答案啊掖举，當(dāng)你有20塊錢的時候，你去買“肥宅快樂水”娜庇，如果你不怕?lián)蔚脑捤危悄銘?yīng)該是可以喝到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("請輸入你的金額：");
//從鍵盤輸入我的錢數(shù)
int money = scanner.nextInt();
// 第一次的錢能喝的汽水瓶數(shù)(一元錢一瓶汽水)
int n = money / 1;
// 我能喝的汽水?dāng)?shù)
int sum = sodaWater(n, 0, 0);
System.out.println("當(dāng)我有" + money + "元時攒发，總共能喝" + sum + "瓶飲料");
}
}
/**
* 用遞歸計算n元錢最多能喝多少瓶汽水
* @param n 飲料瓶數(shù)
* @param bottle 空瓶數(shù)
* @param cap 瓶蓋數(shù)
* @return
*/
private static int sodaWater(int n, int bottle, int cap) {
// 兌換剩下的空瓶數(shù)
bottle %= 2;
// 喝完飲料剩下的空瓶
bottle += n;
// 兌換剩下的瓶蓋數(shù)
cap %= 3;
// 喝完飲料剩下的瓶蓋
cap += n;
if (bottle < 2 && cap < 3) { // 如果空瓶數(shù)<2 并且 瓶蓋數(shù)<3, 那么停止兌換
return n;
}else {
return n + sodaWater(bottle/2 + cap/3, bottle, cap);
}
}
}
04
換個簡單點兒的唄~~
看到這里调塌，笙晨覺得大家好像有點兒暈頭轉(zhuǎn)向的了吧，但是我們還是要解決問題不是惠猿？因此笙晨還找了一個比較簡單點的題目羔砾，甚至我們直接用 n 來表示，好像這樣就不需要像前面那樣偶妖，那么大張旗鼓的動用巨大的精力去算了吧姜凄，讓我們一起來看看是什么題目——
一塊錢一瓶汽水，喝完之后兩個空瓶換一瓶汽水趾访。若現(xiàn)在你有n元錢态秧，那你最多能喝多少瓶汽水？
貌似很多小伙伴們看到這個題目都會隨手拿張打草紙開始寫了吧：
經(jīng)過以上分析我們可以得出扼鞋，這是一個首項為1申鱼，公差為2的等差數(shù)列，也就是說：當(dāng)你有n元錢時云头，在你不怕?lián)蔚那闆r下捐友，最多能喝到（2n-1）瓶“肥宅快樂水”。
05
如果用代碼如何解決呢 溃槐？匣砖？
要想用代碼來解決這個問題，我們首先要試著來分析一下這個題目（我們暫時先不考慮換不完的問題)：
當(dāng)你有n元錢的時候，你買了n瓶汽水猴鲫，喝完之后可以剩下n個空瓶砌溺；
然后你又用n個空瓶，換了n/2瓶汽水变隔，喝完之后可以剩下n/2個空瓶规伐；
然后你又用n/2個空瓶，換了(n/2)/2瓶汽水匣缘，喝完之后你又剩下了(n/2)/2個空瓶猖闪；
……
以此類推，最后你用2個空瓶肌厨，換了一瓶汽水培慌，然后喝完汽水，剩下最后一個空瓶柑爸，因為這時你只剩下了一個空瓶了吵护，換不了，所以就直接扔掉了表鳍。
看完上面笙晨的分析馅而，有沒有覺得這似乎是一個循環(huán)往復(fù)，周而復(fù)始的問題譬圣？
當(dāng)你拿到汽水瓮恭，喝掉之后，再去用空瓶換汽水厘熟，而且當(dāng)最后你只有一瓶汽水的時候屯蹦，兌換結(jié)束，這想不想是一個中止條件绳姨？
好啦登澜，這個題目到這里基本上就可以算是分析完畢，接下來我們便可以開始擼代碼了——
/**
* 計算最多能喝多少瓶汽水飘庄，并返回這個值
* @param n 表示有n瓶汽水
* @return
*/
private static int soda(int n) {
if (n == 1) {
// 遞歸終止條件脑蠕，當(dāng)還有一瓶飲料的時候只能喝一瓶,不能再換了
return 1;
}else if(n % 2 == 0) {
// 偶數(shù)瓶，這時空瓶剛好能夠換完
return n + soda(n/2);
}else {
// 奇數(shù)瓶竭宰，這一次剩下的一個空瓶子剛好和最后一次的一個空瓶子能換一瓶飲料空郊，所以要+1
return n + 1 + soda(n/2);
}
}
至于為什么在奇數(shù)瓶的時候還要+1，大家可以自己畫畫圖理解一下啦（我才不會說是我不想畫了呢）其實通過簡單的畫圖切揭，我們可以發(fā)現(xiàn)：當(dāng)有奇數(shù)瓶時狞甚，再復(fù)雜的情況，也無非就是3瓶時的疊加嘛~
因此廓旬，我們試著在main方法里面調(diào)用一下哼审，來檢驗一下結(jié)果：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for(;;) {
System.out.print("請輸入你的金額：");
// 從鍵盤輸入我的錢數(shù)
int money = scanner.nextInt();
// 第一次的錢能喝的汽水瓶數(shù)(一元錢一瓶汽水)
int n = money / 1;
// 我能喝的汽水?dāng)?shù)
int sum = soda(n);
System.out.println("當(dāng)我有" + money + "元時谐腰，總共能喝" + sum + "瓶飲料");
}
}
Nice！涩盾！讓我們來看一下運行結(jié)果：
但是看到這里十气，笙晨相信有很多小伙伴們或許就會有疑惑了：你為啥非要用遞歸嘞？人家循環(huán)它不香嘛春霍？砸西？
好，既然說了址儒，笙晨滿足你們這個愿望芹枷，我們用循環(huán)來操作一番——
/**
* 用循環(huán)來計算最多能喝多少瓶汽水
* @param n
* @return
*/
private static int soda2(int n) {
// 總共能喝的飲料瓶數(shù)
int sum = n;
// 當(dāng)n==1時循環(huán)結(jié)束，所以n>1
for (; n > 1; n = n/2) {
if (n % 2 == 0) {
sum += n/2;
}else {
// 此次的飲料瓶數(shù)是奇數(shù)瓶就+1
sum += (n/2 + 1);
}
}
return sum;
}
然后莲趣，讓我們將上面main方法中鸳慈，計算喝汽水的方法，直接改為這個方法：
// 我能喝的汽水?dāng)?shù)
int sum = soda2(n);
接著運行一下喧伞，你就會驚奇的發(fā)現(xiàn)：哇哦走芋，他們的結(jié)果是一樣的誒（這里笙晨就不再展示運行結(jié)果了，畢竟結(jié)果都是一樣的嘛）
咦潘鲫？等等翁逞，笙晨突然想到，我們之前不是還用推導(dǎo)公式來著嘛次舌？熄攘？現(xiàn)在為啥不用了呢？非要挨著去分情況討論彼念，我還費那么多事情干啥？浅萧？（我才不會說是當(dāng)時腦子短路了呢）
所以我們就可以直接用前面推導(dǎo)出來的（2n-1）這個公式直接來算了：
/**
* 直接用推導(dǎo)出的數(shù)學(xué)公式（2n-1）來計算
* @param n
* @return
*/
private static int soda3(int n) {
return 2 * n - 1;
}
接著調(diào)用逐沙，讓我們來調(diào)用測試一下：
// 我能喝的汽水?dāng)?shù)
int sum = soda3(n);
Nice！洼畅！相信大家都運行出結(jié)果來了吧吩案，是不是跟之前的結(jié)果都是一樣的？好吧帝簇，請數(shù)學(xué)爸爸再愛我一次吧~~（請收下我的膝蓋）
其實當(dāng)我們在之前分情況討論徘郭，以及用公式來敲代碼的過程中，基本上也會出現(xiàn)一些問題丧肴，比如：
（1）當(dāng)我們用分情況討論的時候残揉，我們會發(fā)現(xiàn)，其中當(dāng)奇數(shù)瓶時芋浮，里面的那個+1實在是不太好理解抱环，這也就導(dǎo)致了代碼的可讀性較差；
（2）但是如果我們改成用公式來計算的話，Emm……這辦法好是好镇草，但是你能保證你的智商一直在線眶痰？？畢竟咱有時候不會推導(dǎo)數(shù)學(xué)公式疤萜 （笙晨才不會說自己笨呢竖伯，略略略）；
（3）還有一點我們就牽扯到了一丟丟的數(shù)據(jù)結(jié)構(gòu)的知識了因宇，雖說對于這個題來說黔夭，遞歸和循環(huán)的解法相比似乎沒有什么兩樣，甚至我們仔細想一下羽嫡，這個題如果用遞歸解決本姥，甚至都不如直接用循環(huán)來的好，畢竟遞歸的空間復(fù)雜度要更高嘛（你又要人家入棧杭棵，又要人家出棧的婚惫，空間復(fù)雜度能不高嘛？魂爪？）
但是我們回頭細思先舷，在每次周而復(fù)始的過程中，不但有汽水這個變量滓侍，還有空瓶這個變量啊蒋川，那我們?yōu)楹尾辉囍苯?strong>引入空瓶這個變量來解決問題呢？話不多說撩笆，代碼走起——
/**
* 用遞歸計算出最多能喝多少瓶汽水
* @param n 飲料瓶數(shù)
* @param bottle 空瓶數(shù)
* @return
*/
private static int soda1(int n, int bottle) {
// 兌換剩下的空瓶數(shù)
bottle %= 2;
// 喝完飲料剩下的空瓶數(shù)
bottle += n;
if (bottle < 2) { // 如果空瓶數(shù)<2捺球，停止兌換
return n;
} else {
return n + soda1(bottle/2, bottle);
}
}
讓我們直接調(diào)用測試一下：
// 我能喝的汽水?dāng)?shù)
int sum = soda1(n, 0);
Nice！ＯΤ濉氮兵！結(jié)果竟然也是跟之前的一樣！４跤恪泣栈！這下才可以算是完美了一丟丟，這時候我們的代碼可讀性也比之前要強很多了嗎弥姻，而如果要是用循環(huán)來控制兩個變量南片，來解決這個問題的話，那么代碼很可能又會變得非常復(fù)雜庭敦。
好了疼进，到這里基本上笙晨能搜集到的關(guān)于這個題的一些解法基本上就是這么多了，后續(xù)也希望有小伙伴們可以跟笙晨一起討論哦~~
PS：寫 在 最 后
至此螺捐，笙晨今天跟大家分享的關(guān)于遞歸里面的“肥宅快樂水”問題颠悬，也就算是告一段落了矮燎，遞歸這東西說簡單也簡單，說難也還真的挺難的赔癌，或許后續(xù)笙晨也會專門抽出一些時間來跟大家詳細的聊一聊“遞歸”的那些事兒诞外，今天我們也就到此為止吧。
哦灾票，對了峡谊，老師下課前貌似都是總結(jié)一下今天講到的一些知識點，所以笙晨也來簡單的總結(jié)一下吧刊苍，就讓笙晨來簡單總結(jié)一下“遞歸”和“循環(huán)”的區(qū)別吧：
（1）遞歸：其實遞歸就是程序調(diào)用自身的一種編程技巧既们。在Java中具體表現(xiàn)為方法在方法體內(nèi)部直接或間接調(diào)用方法本身。他可以說是比較懶的啦正什，每次做事情都會留一些啥纸，然后再回來，反序地把這些剩下的事情一一做完婴氮。
說的簡單粗暴點斯棒，就像是你媽讓你去掃個地，你第一遍卻沒有掃干凈主经，但是又迫于無奈荣暮，想想晚上的那口晚飯，你干脆心一橫罩驻，直接用拖把反方向回來再拖一遍穗酥；
（2）循環(huán)：循環(huán)就是重復(fù)性的執(zhí)行某段程序。但是人家循環(huán)跟遞歸還又不太一樣惠遏，貌似還是個直男砾跃，直接就一次性干脆利落的把活兒全都干完了，之后便永不回頭爽哎，干脆理都不理你了……
好啦蜓席，今天笙晨跟大家就分享到這里了，哦课锌，不對還有一點，笙晨還想說一下祈秕，就是有些小伙伴們之前提到的一點：既然遞歸能干的事情渺贤，人家循環(huán)也能干啊，你為啥偏偏要選遞歸而不用循環(huán)嘞请毛？
其實雖說遞歸能干的事情志鞍，循環(huán)貌似也能干，甚至好像會更簡單方仿，但是我們要知道一點：循環(huán)能解決的問題固棚，遞歸一般也能解決统翩；但是遞歸能解決的問題，循環(huán)就不一定能解決了此洲。畢竟人家遞歸是運用的是“分而治之”的思想厂汗，把一個復(fù)雜的原問題拆分成若干個子問題來解決，這里面妙就妙在遞歸能用有限的語句表現(xiàn)出無限的過程呜师。但是如果我們不了解遞歸娶桦，可能也就掌握不了快排、歸并排序等算法了汁汗，這些都是些后話了衷畦，咱們以后再說。
好啦好啦知牌，這次是真的沒了祈争，笙晨今天就跟大家聊到這里了，大家如果對遞歸有興趣的話角寸，還可以直接通過度娘等方式菩混，去自己學(xué)習(xí)一下哦~~
我們幾天，甚至是好幾天后再見咯袭厂，bye~~
PS：原文鏈接：聊聊遞歸“肥宅快樂水”的那些事兒
看完記得關(guān)注【笙晨閑談】微信公眾號墨吓，不定期更新“計算機”類的相關(guān)干貨，以及閑談類的文章纹磺。只要你關(guān)注帖烘，就會有故事哦~
