猴子吃桃这个问题几乎是每个 Java 初学者都会撞上的经典递归题。我自己在带新人写程序时也最爱拿它当引子题目读起来就是个数学应用题猴子第一天摘了若干个桃当天吃了“一半”还不过瘾又多吃了1个第二天早上又把剩下的吃掉一半再多吃了1个之后每天早上都按这个规律来。题目描述到“到第10”这里断了按最常见的完整版本是“第10天早上它想再吃时发现只剩下1个桃子”然后问第一天它到底摘了多少这题表面是求一个数实际考察的是三件事——把中文描述抽象成数学关系的能力、想到“逆推”这个关键操作的能力、以及写出能跑的 Java 代码的能力。下面我把完整思路、三种实现方式和实操中经常踩的坑一次性说清楚。1. 题目拆解先读懂题再动手写码1.1 补全题目先确定边界条件很多初学者拿到这题就急着写代码结果写出来的循环和递归五花八门但答案各有各的错。原因很简单题目没读懂。我们先把残缺的描述补全成完整版猴子第一天摘下若干个桃子当即吃了一半还不瘾又多吃了一个。第二天早上又将剩下的桃子吃掉一半又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时见只剩下一个桃子了。求第一天共摘了多少关键信息是“到第10天早上只剩1个桃子”。这句话的意思是第10天早上还没吃筐里就只剩1个了。也就是说我们已知的不是“吃完之后剩1个”而是“第10天开始时有1个”。这个边界条件直接决定答案后面我会专门讲如果理解成“吃完后剩1个”结果会差多少。1.2 把文字翻译成递推公式数学里处理这类“每天按固定规律变化”的问题最顺手的工具是递推。设f(n)表示第 n 天早上还没吃之前筐里的桃子数那么题干描述翻译过来就是第 n-1 天早上有 f(n-1) 个 当天吃掉 f(n-1)/2 1 个 剩下 f(n-1) - (f(n-1)/2 1) f(n)整理一下f(n-1) - f(n-1)/2 - 1 f(n) f(n-1)/2 - 1 f(n) f(n-1) (f(n) 1) * 2这就是最核心的递推式前一天的桃子数 后一天的桃子数 1× 2。再加上已知的边界条件f(10) 1整个问题就完整了。别看这个式子简单它的推导过程才是这题真正的考点能不能把“吃了一半又多吃一个”精确地写成减法表达式很多人第一步就在这里栽了。1.3 为什么这道题必须“倒着算”拿到递推式之后有一个方向问题需要想明白顺推行不行如果从第1天开始推我们压根不知道f(1)是多少——而f(1)恰好就是题目要求的东西。顺推等于带着一个未知数往前跑虽然也可以用方程解但代码写起来绕、不直观、还容易错。倒着推就不一样了。第10天的桃子数是确定的1个从这个确定值出发每天往回还原一步9 次运算就能得到第1天的值。这就像你手里有一串钥匙要按顺序挂好但你只记得最后一把长什么样那就从最后一把往前倒着挂每一步都有确定依据不会乱。在程序里“从确定的边界条件出发沿着递推关系反向回溯”是一类非常通用的解题策略猴子吃桃只是它的入门载体。2. Java 代码实现三种写法一次讲透2.1 循环逆推最推荐的第一版理解了逆推思路循环版本的代码其实只有几行。我建议所有初学者第一版就写这个因为它把“反向还原”的过程暴露得最清楚public class MonkeyPeach { public static void main(String[] args) { int day 10; // 从第10天开始往回倒 int peaches 1; // 第10天早上只剩 1 个 while (day 1) { peaches (peaches 1) * 2; // 还原前一天的桃子数 day--; } System.out.println(第一天摘下桃子总数 peaches); } }运行结果第一天摘下桃子总数1534这个版本里最容易写错的是循环条件。注意day 1而不是day 0第10天的值一开始就已经手写进去了不需要再算一次所以循环只在 day 从 10 变到 2 时执行一共 9 次迭代分别求出第9天到第1天的值。有人会问“为什么不是 10 次”因为第10天的状态是已知输入不是计算产物。如果把条件写成day 0会多算一步得出 3070——这个错我见很多新人犯过后面踩坑环节还会细说。2.2 递归实现体会“递推回头”的过程循环版本虽然简单但猴子吃桃在教材和面试里基本都是递归题。递归写法直接镜像数学定义几乎不用思考过程public class MonkeyPeachRecursion { public static int f(int n) { if (n 10) { return 1; } return (f(n 1) 1) * 2; } public static void main(String[] args) { System.out.println(第一天摘下桃子总数 f(1)); } }执行过程大概是这样的f(1)需要f(2)f(2)需要f(3)……一路要到最后f(10)直接返回 1然后结果像弹簧一样逐层回弹f(10) 1 f(9) (1 1) * 2 4 f(8) (4 1) * 2 10 ... f(1) (766 1) * 2 1534这个“先一路递下去再一路归回来”的过程就是递归的本质。很多新手老觉得递归玄乎其实把它拆成“终止条件 递推关系”两部分看就清楚了n 10对应终止条件(f(n 1) 1) * 2对应递推关系。注意这里的递推公式形态它是“由后一项推前一项”和正向的“由前一项算后一项”正好相反这正好是逆推思想的递归表达。2.3 参数化写法把天数和剩余数交给调用方循环和递归版本都写死了“第10天剩1个”。如果题目改成“第15天早上剩3个桃子”就得重新改代码。更规范的做法是把天数、末状态的桃子数都抽成参数public class MonkeyPeachParam { // 从 startDay 这天开始算已知 endDay 这天早上剩 left 个 public static int calc(int startDay, int endDay, int left) { if (startDay endDay) { return left; } return (calc(startDay 1, endDay, left) 1) * 2; } public static void main(String[] args) { System.out.println(第10天剩1个第一天摘了 calc(1, 10, 1)); System.out.println(第8天剩3个第一天摘了 calc(1, 8, 3)); System.out.println(第15天剩2个第一天摘了 calc(1, 15, 2)); } }输出第10天剩1个第一天摘了 1534 第8天剩3个第一天摘了 316 第15天剩2个第一天摘了 49150参数化之后这个代码就不再是“某一道题的答案”而是一个可复用的工具方法。我把这种方法也叫“把答案交给调用方”在笔试里遇到稍微变形的递推题能用参数化写法现场生成通用解比临时改逻辑要稳得多。3. 正向验算与完整运行记录3.1 写一个正向模拟程序反推验证逆推算出来 1534很多新手到这里就收工了。但我强烈建议再写一个正向模拟程序从 1534 开始顺着规则吃一遍看能不能吃到第10天正好剩1个。这不只是验证答案更是训练“用代码模拟现实过程”的能力public class MonkeyPeachCheck { public static void main(String[] args) { int peaches 1534; for (int day 1; day 9; day) { System.out.println(第 day 天早上有 peaches 个); peaches peaches - (peaches / 2 1); // 吃掉一半加一个 } System.out.println(第10天早上有 peaches 个); } }输出第1天早上有 1534 个 第2天早上有 766 个 第3天早上有 382 个 第4天早上有 190 个 第5天早上有 94 个 第6天早上有 46 个 第7天早上有 22 个 第8天早上有 10 个 第9天早上有 4 个 第10天早上有 1 个正向模拟走出来的结果和第10天剩1个完全对得上说明逆推答案没算错。这个习惯非常值得保留递推题写完最好用正向循环反向验证一遍。逆向逻辑和正向逻辑互相独立两个方向结果一致代码才真正可信。3.2 顺推与逆推的数据对照把正向吃桃过程和逆推还原过程放在一起看会更直观天正向当天早上的桃子数当天吃掉的数量剩下给次日11534767 1 7687662766383 1 3843823382191 1 192190419095 1 969459447 1 484664623 1 242272211 1 12108105 1 64942 1 31101还没吃-这张表值得多看两遍。第1天到第9天每行都是由上一行推导出来的正向是“减去一半再减一”逆向是“加一后乘二”。注意看第9天早上只有4个桃吃掉 4/2 1 3 个剩下1个撑到第10天早上——数学上恰好整除没有出现半个桃这正是题目隐含的约束条件。3.3 变量类型怎么选int 够用吗1534 这个答案用int存绰绰有余但如果你把参数化版本的天数改大情况就完全不同了。递推式f(n-1) (f(n) 1) * 2本质是指数增长桃子数大约按 2 的幂次膨胀。我算过到第10天剩1个初始约 1534到第20天剩1个初始大约 150 万到第30天就开始逼近 16 亿了。Java 的int最大值是 2147483647。实际跑一下参数化版本把endDay改成 31 看看System.out.println(calc(1, 31, 1));结果变成负数这就是典型的int溢出。所以只要天数可能超过 30就应该把返回值类型升级为longpublic static long calcLong(int startDay, int endDay, long left) { if (startDay endDay) { return left; } return (calcLong(startDay 1, endDay, left) 1) * 2; }long最大到 9223372036854775807大概能撑到第 62 天左右。如果题目真变态到让你算第 100 天那就得用BigInteger了。作为参考在面试场景里把类型范围聊清楚往往比把题算对更能加分因为这体现你写代码时会考虑数据范围。4. 常见问题与踩坑实录4.1 边界条件理解偏差第10天“之前”剩1个还是“之后”剩1个这是我在群里见过最多的坑。题目原意是“到第10天早上想再吃时见只剩下一个桃子”也就是第10天开始时有1个。但如果有人把题意理解成“第10天也照常吃了一半加一个吃完后还剩1个”那边界条件就完全不同了。这种情况下第10天开始时有 x 个满足x - (x/2 1) 1解出来x 4。然后继续逆推f(10) 4 f(9) (4 1) * 2 10 f(8) 22 f(7) 46 f(6) 94 f(5) 190 f(4) 382 f(3) 766 f(2) 1534 f(1) 3070答案直接翻了一倍多。所以拿到题第一件事就是确认“第10天”指的是吃之前的存量还是吃之后的存量。别小看这一步真实笔试里很多人都死在这上面——不是不会写递归而是边界条件读错了。4.2 循环次数多一少一经典 off-by-one循环逆推版本的经典错误是把条件写成while (day 0)。比如这段int day 10; int peaches 1; while (day 0) { peaches (peaches 1) * 2; day--; }跑出来结果是 3070刚好是在 1534 的基础上又逆推了一天第0天多算了一轮。正确的做法是画一个“状态分布图”第10天已知不需要进入循环去算它第9天到第1天这9个值才是循环要算的。凡是出现答案正好是正确答案两倍左右的情况先怀疑循环多跑了一次。这也提醒我们写循环时想清楚“循环体每执行一次会产生哪个结果”而不是凭感觉数次数。4.3 递归终止条件丢失与栈溢出递归版本最大的风险是忘记写终止条件。比如写成public static int f(int n) { return (f(n 1) 1) * 2; }这段代码会在运行时无限调用自己最终抛出StackOverflowError。猴子吃桃这个递归深度只有9层不太会触发栈溢出但如果你把参数化版本的天数改成几千递归深度也会变成几千照样会栈溢出。所以我平时建议递归适合深度可控的场景深度不可控就用循环。面试时如果考官追问“这个递归会不会栈溢出”能答出“本题深度固定为9层不会溢出但通用场景要警惕深度过大”基本就是加分项。4.4 除法取整在变式题里的隐患正向模拟里用了peaches / 2 1Java 的整数除法会直接截断小数。本题数据保证每一步都是偶数所以不存在问题。但如果你改一下题目参数比如“第8天剩3个”之类的算出来的中间值可能不是偶数整数除法就会出问题。我用参数化版本验证过几个组合发现有些参数组合在正向模拟时会出现“剩半个桃”的尴尬情况这是因为逆推公式(x 1) * 2永远产生偶数但正向模拟的除法和它并不总是自洽。遇到这类变式题要么改用double类型做正向验证要么在题目描述里确认“桃子数始终是整数”。这个坑很隐蔽属于“题目本身不严谨”导致的写代码时最好把假设条件在注释里写清楚// 假设每天吃之前桃子数均为偶数保证整除4.5 常见问题速查表症状可能原因处理方式答案变成 3070循环多跑一次 / 把第10天也算进去了检查循环条件是否为day 1答案变成 1535 之类“差一点”的数对“吃了一半”的含义理解错误重新核对公式剩 原 - 原/2 - 1递归运行报 StackOverflow缺少终止条件检查if (n 10) return 1;第30天结果变负数int 溢出改用long或BigInteger正向验证和逆推结果对不上边界条件写错 / 除法取整问题确认“第N天”指“开始”还是“结束后”5. 变式题与解题框架5.1 通用模型如果“每天多吃 c 个”怎么办猴子吃桃只是递推模型的一个特例。把“多吃一个”换成“多吃 c 个”递推式就变成f(n-1) - (f(n-1)/2 c) f(n) f(n-1) (f(n) c) * 2代码只需要把加1改成加 cpublic static long calc(int startDay, int endDay, long left, int extra) { if (startDay endDay) { return left; } return (calc(startDay 1, endDay, left, extra) extra) * 2; }这个小小的改动就把一道题扩展成了一类题。以后再遇到“每天吃三分之一再加两个”“每天吃剩下的三分之二再减一个”之类的表述核心思路一模一样先写出“当天剩余 前一天开始数 - 按规则吃掉数”的表达式再解出f(n-1)关于f(n)的公式最后从已知的末状态逆推回来。5.2 通项公式直接数学求解逆推写代码当然没问题但如果你愿意还能把这道题直接算成闭式公式。由f(n-1) 2(f(n) 1)展开f(1) 2^9 * f(10) 2^9 - 1? // 等等这里需要严格推导严格推导一下。递推式f(k) 2f(k1) 2从f(10)一直代入到f(1)f(1) 2^9 * f(10) 2 * (2^9 - 1) 512 * 1 2 * 511 512 1022 1534写成通用形式就是如果第 n 天早上剩 m 个那么第一天有2^(n-1) * m 2^n - 2个。这个公式在答面试题时可以作为锦上添花的一笔证明你不仅会写代码还能从数学角度把问题彻底吃透。不过我要提醒一句通项公式适合天数和末状态固定的场景一旦题目改成“每天吃三分之一”或者“每天吃数量递减”公式就要重新推而递推代码反而更通用。所以在面试里我通常先讲递推代码再用通项公式作补充而不是一上来就抛公式。5.3 这类题在面试和作业里怎么考猴子吃桃最常见的出现场景是课堂作业、期末考试填空题、初级面试的“热身递归题”。它不会单独作为一道大面试题但考官可能会在你解完后追加几个问题“为什么不用正向循环直接求解”——答正向缺初始值只有末状态确定天然适合逆推。“递归和循环两种写法有什么差别”——答递归代码更贴近数学定义、可读性好但每次调用都有函数栈开销循环省资源。本题深度固定两者皆可。“如果把第10天改成第100天你的代码还成立吗”——答递归深度会到 99 层仍然安全Java 默认栈深度通常上千但数值要用 long/BigInteger 承载。“能不能写出数学通项”——能就是上面的2^(n-1) * m 2^n - 2。我个人在实际带人写这题时还有一个习惯让学习者必须写出“正向验算代码”。理由是绝大多数人在逆推时都能写对但很少有人主动去验证结果一旦养成“算完必须反推验证”的习惯后面做任何递推、动态规划题目都会少走很多弯路。最后分享一个小技巧遇到任何递推题先在纸上把前三个值手算出来用它们做测试用例如果你的代码跑出的前三个值和手算一致最后答案基本就不会跑偏。猴子吃桃就是一个典型到不能再典型的“纸上先算、代码后写”的例题把这个流程跑通一次你收获的不只是 1534 这个数字而是一套可以复用的解题框架。