我面试Java初级岗时经常拿一道“五个人报年龄”的递归题开聊。题目本身很简单五个人坐成一排后一个人总比前一个人大两岁第一个人10岁问第五个人多少岁。你让候选人写个Java方法很多人十秒钟就能写完但真让他讲清楚递归在计算机里是怎么一步步算出来的一半以上就卡壳了。这篇文章就把这道五人年龄计算的递归题彻底拆开——从数学递推式讲到Java代码落地再讲清楚JVM调用栈里到底发生了什么最后聊一聊这类递归题的常见坑和它在真实工程里的位置。适合刚开始学Java递归的新手也适合准备Java面试想在原理层面多拿分的求职者。1. 一道“报年龄”的递归入门题先弄清楚它到底在问什么1.1 题目原貌五个人后一个总比前一个大两岁原题大概是这么说的有5个人坐在一起问其中一个人多少岁他说比旁边那位大2岁再问旁边那位又说比再旁边那位大2岁……这样一直推到第1个人他说自己10岁。现在要你求出第5个人的年龄。不要急着写代码先手算第1个人10岁第2个人就是12岁第3个人14岁第4个人16岁第5个人18岁。这道题本质上是一个等差数列只是它用“对话链”的形式把条件给出来了。这里有个小细节有的书里会说“第5个人比第4个人大2岁”有的会说“第2个人比第1个人大2岁”方向不同但本质一样都是第n个人比第n-1个人大2岁。做题前先把题干里的“谁比谁大”这个方向捋清楚不然代码写着写着基准条件和递推式就对不上。为什么要强调先手算因为递归题的输出结果是可以预判的。你先知道答案是18后面无论用递归、循环还是打印跟踪都能验证代码没写歪。如果一个人上来就写代码连结果是多少都说不出来那他对题意的理解大概率是有问题的。1.2 递归三大要素在这道题里的对应关系递归这东西很多教材一上来就讲“函数调用自身”这个定义没错但对新手来说太空了。我更愿意把递归理解成一句话把一个大问题拆成一个更小的问题而这个小问题的解法和大问题完全一样只是规模变小了一直小到某个可以直接回答的程度就停。这道题里正好有递归需要的三个要素。第一个是递推公式第n个人的年龄 第(n-1)个人的年龄 2第二个是基准条件第1个人的年龄 10不需要再往前问了第三个是收敛方向每次调用年龄的编号都减1从5开始一路退到1一定能在有限步内停下。注意这三个要素缺一不可。没有递推公式方法没法自我调用没有基准条件调用永远不会停没有收敛方向即使写了基准条件也可能永远够不到。后面讲踩坑时你会发现几乎所有的递归Bug都能归到这三条里。2. 从数学递推式到Java代码先写公式再写方法2.1 用函数视角写出递推公式如果定义一个函数age(n)表示第n个人的年龄那么题目给出的条件可以翻译成这样age(1) 10 age(n) age(n - 1) 2 (n 1)这两个式子一行是出口一行是递推写完这个公式再动手碰键盘代码基本就是公式的逐行翻译。很多同学一上来就写if-else其实if-else就是从这两个式子来的公式都没列好if条件当然也容易写错。我用“函数视角”这个词是想强调age(n)这个名字在你脑子里应该是一个完整的映射关系输入一个整数n输出这个人的年龄。输入5输出18输入1输出10。递归不过是用“调用自己”的方式来实现这个映射。这跟数学里的递推数列是一回事只是换成了Java语法。2.2 核心Java实现一个方法解决问题public class AgeRecursion { // 返回第 n 个人的年龄 public static int age(int n) { if (n 1) { return 10; } return age(n - 1) 2; } public static void main(String[] args) { int result age(5); System.out.println(第5个人的年龄是 result 岁); } }运行结果第5个人的年龄是18岁。这段代码短得没什么好解释的我反而想提醒两件容易被忽略的事。第一age方法在return语句里调用了自己说明这里才是“递归发生”的地方第二age(n - 1) 2这个表达式的执行顺序是先计算出age(n - 1)的值再加2不是先加2再递归。这个顺序在后面的调用栈部分非常关键。至于数据类型这里用int完全够用年龄不会超过int范围。有的初学者喜欢什么都用long没必要一个年龄字段用int才是最自然的。2.3 加日志看执行轨迹先一头扎到底再逐层返回对于第一次接触递归的人只看代码想象不出来运行过程。我建议你在递归方法里加两行打印把它每一层的进出都摆在眼前public static int ageWithTrace(int n) { System.out.println(开始计算 age( n )); if (n 1) { System.out.println(触底age(1) 10开始返回); return 10; } int result ageWithTrace(n - 1) 2; System.out.println(返回age( n ) age( (n - 1) ) 2 result); return result; }直接调用ageWithTrace(5)控制台会打印出这样一条轨迹开始计算 age(5) 开始计算 age(4) 开始计算 age(3) 开始计算 age(2) 开始计算 age(1) 触底age(1) 10开始返回 返回age(2) age(1) 2 12 返回age(3) age(2) 2 14 返回age(4) age(3) 2 16 返回age(5) age(4) 2 18注意一个反直觉的点打印“开始计算”的顺序是5、4、3、2、1而打印“返回”的顺序是2、3、4、5。这就是递归最核心的执行特征——先一路下探到基准条件然后一层一层往回带结果。很多初学者以为递归是边往下走边累加其实并不是真正做加法的是在“返回”的路上。看到这段输出你对“递”和“归”两个字应该就有感觉了递是从外往里钻归是从里往外带答案。3. 递归在JVM里的运行账本调用栈的压栈与弹栈3.1 栈帧是什么每次方法调用都会留下一个待办记录前面用日志看到了结果但日志只展示现象。要解释为什么是这个顺序需要知道JVM调用方法时底层的栈行为。JVM给每个线程分配了一块栈内存专门记录方法调用过程中的中间状态。每调用一个方法就会在栈顶压入一帧这一帧就叫栈帧里面保存了方法的参数、局部变量、中间计算结果以及方法结束后要返回到哪里。方法执行完帧就从栈顶弹出控制权交还给调用者。栈这种结构后进先出。你可以把它想成食堂里叠在一起的餐盘最后放上去的最先被拿走。这个特性决定了方法调用的返回顺序后调用的方法先返回。递归表面上只有一个方法在调用自己实际上每一次调用都会产生一个独立的栈帧压入同一个栈。方法还是那个方法但每一层的参数n不同存的状态也不同。3.2 五个年龄的栈帧推演从压栈到弹栈的完整过程我们用age(5)的调用过程过一遍。最开始main方法调用age(5)age(5)的栈帧入栈。age(5)里要计算age(4)2于是age(4)的栈帧入栈age(4)又要age(3)age(3)要age(2)age(2)要age(1)这样栈里自底向上依次是main、age(5)、age(4)、age(3)、age(2)、age(1)。执行到哪一步栈里的内容自底向上说明main调用age(5)main - age(5)age(5)压栈开始执行age(5)调用age(4)main - age(5) - age(4)age(5)等待age(4)结果age(4)调用age(3)main - age(5) - age(4) - age(3)继续往下压age(3)调用age(2)main - age(5) - age(4) - age(3) - age(2)继续往下压age(2)调用age(1)main - age(5) - age(4) - age(3) - age(2) - age(1)压到最深处age(1)命中基准返回10main - age(5) - age(4) - age(3) - age(2)age(1)弹栈带回10age(2)算出12并返回main - age(5) - age(4) - age(3)age(2)弹栈带回12age(3)算出14并返回main - age(5) - age(4)age(3)弹栈带回14age(4)算出16并返回main - age(5)age(4)弹栈带回16age(5)算出18并返回mainage(5)弹栈main拿到18这张表里最关键的一步是第6行age(1)命中基准条件后它是直接返回10而不需要再调用别人。这一下就像推倒了多米诺骨牌上层的age(2)拿到10后加2等于12再返回给age(3)age(3)加2等于14……依此类推。所以你可以把基准条件理解为递归链上唯一的“结果来源”。没有它整个调用链就没有任何一个方法能结束栈会越压越高直到压爆。3.3 从栈的角度看递归的空间开销age(n)递归n层栈里最多同时出现n个栈帧内存开销是O(n)。对这道题来说n5小得可以忽略但如果哪天你要算age(100000)就需要十万个栈帧同时存在的空间。而用for循环计算同一个递推式只需要一个变量存当前年龄空间是O(1)。这就是经常说的“递归不是免费的”。它换来的是代码简洁、逻辑直白付出的是额外的栈空间。理解了栈帧模型你就能理解为什么有些网上代码跑着跑着抛出StackOverflowError——不是电脑坏了是栈真的被塞满了。4. 第一次写递归最容易踩的坑基准条件、栈溢出与参数陷阱4.1 忘写基准条件StackOverflowError是怎样产生的新手第一版经常写成这样public static int age(int n) { return age(n - 1) 2; }这个版本看着只比正确版本少了个if编译能过运行时立刻炸。age(5)会去调age(4)age(4)调age(3)……一直往后调直到所有整数被减到负数还是没停。JVM的栈内存是有限的栈帧一层层往上叠超过上限就会抛出StackOverflowError。这个异常根本不是“算错了”而是“停不下来”。有些同学遇到它第一反应是检查加法有没有写错方向完全错了。你应该先检查递归方法有没有基准条件每次调用有没有朝基准条件靠近4.2 基准条件写错但不报错结果悄悄算错比栈溢出更隐蔽的是基准条件“写偏了”。比如你想着第1个人10岁手一抖写成public static int age(int n) { if (n 0) { return 10; } return age(n - 1) 2; }从n5开始会一路减到0返回10程序不会报错。但你算一下age(1)变成age(0)212也就是说第1个人的年龄变成了12和题意“第1个人10岁”就矛盾了。最终age(5)返回20相当于把“第0个人10岁”当成了基准整体往后多算了一层。这类问题为什么难发现因为答案看起来好像也合理只是大了2岁。不细看根本不会怀疑。所以我在写递归前一定先把age(1)10和age(2)12这两个值想清楚再写基准条件写完先跑一下age(2)能对再往上测。还有一种更隐蔽的基准条件用了n 1如果你的参数不小心传了0或负数也会进入基准条件返回10。虽然本例中调用方一般不会传非法值但这种“宽松”会让问题更晚暴露。工程上我会建议在方法入口加一句参数校验比如if (n 1) throw new IllegalArgumentException(...)至少让非法输入第一时间报出来。4.3 方向写反永远够不到基准条件的无限递归除了基准条件本身递归调用参数的方向也很容易翻车。比如有人会把age(n-1)写成age(n1)public static int age(int n) { if (n 1) { return 10; } return age(n 1) 2; }调用age(5)后n还要继续6、7、8……一路往上走永远到不了1照样栈溢出。要检验方向对不对只需要盯住一句话每次调用自己时参数都应该离基准条件更近一步。沿着递推式n - n-1n最终能收敛到1这个方向就是对的。我甚至会在注释里写一行“调用方向n递减到1”不是写给人看的是写给自己下次改代码时看的。递归代码越短越要防着自己手滑。4.4 深度是硬约束-Xss能调但别滥用可能有人听说可以用JVM参数-Xss调大栈空间于是遇到栈溢出就改参数。比如java -Xss2m AgeRecursion。这确实能缓解但不是根治。栈空间是从操作系统的线程内存里切出来的调得过大要么浪费内存要么在容器环境里直接起不了线程。正常工程实践里如果预估递归深度可能上万第一选择应该想办法换成循环或者用显式栈。给你一个体感参考JVM默认栈大小在不同平台上常见是512KB到1MB具体要看JDK版本和平台。一个栈帧的占用跟方法局部变量、参数有关简单方法可能几十字节复杂方法几百字节。所以几千层的递归已经有点危险上万层的简单递归就可能触发栈溢出十万层基本必爆。五人年龄这种题深度只有5怎么跑都没事真正给线上系统写代码时心里要时刻记着这个深度账。5. 走出这一步看递归的边界尾递归、循环重写与记忆化5.1 这道题是尾递归吗Java为什么不优化尾递归总有人会问既然递归调用的最后可以改成return age(n - 1)这样的形式那是不是叫尾递归Java会自动优化成循环先说结论Java语言规范没有要求对尾递归做优化目前主流JVM实现也不会主动做尾递归优化。看一下最初的写法return age(n - 1) 2。在递归调用返回之后还得做一次加2所以它不是尾递归。为了让它变成尾递归通常要引入一个累加参数public static int ageTail(int n, int acc) { if (n 1) { return acc; } return ageTail(n - 1, acc 2); }ageTail(5, 10)会得到18。这个写法把“加2”放进了下一次调用的参数里方法返回时不再有任何额外计算形式上确实符合尾递归定义。但在Java里它照样会压5层栈调用链依然是一层一层先压栈再弹栈。真正会做尾递归优化的语言比如某些函数式语言会把这个调用优化成循环复用同一个栈帧。Java没有这个能力所以Java里写尾递归更多是为了整洁表达不能指望性能提升。如果你追求性能直接上循环。5.2 用for循环写同一道题什么场景该放弃递归同一个递推式循环版写出来是这样public static int ageByLoop(int n) { int age 10; for (int i 1; i n; i) { age 2; } return age; }逻辑完全一致但空间只有O(1)。所以如果题目只是这种线性的递推关系循环永远是更务实的选择。递归在这里更大的价值是教学它把递推公式和代码之间的映射讲清楚了。什么时候该用递归我的判断标准是当问题本身的定义就是递归的或者说用循环写反而要自己维护一个栈时递归才显示出优势。比如遍历一棵目录树循环写法要手工维护一堆节点列表递归写法三行结束。那种情况下递归的简洁价值远大于那点栈开销。这和你是不是看起来很“高级”没有关系递归不是银弹循环也不是保守。选型看场景。5.3 记忆化递归遇到重复子问题时的升级方案五人年龄这个递推很特殊每个age(n)只依赖它前面一个age(n-1)不重复计算。但你把递推改成斐波那契那种问题就不一样了。斐波那契的朴素递归写法public static int fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); }这里fib(5)会展开成一棵调用树fib(3)被算两次fib(2)被算三次n一大指数级爆炸。这时候可以引入一个memo数组把已经算过的结果存起来public static int fib(int n, int[] memo) { if (n 1) { return n; } if (memo[n] ! 0) { return memo[n]; } memo[n] fib(n - 1, memo) fib(n - 2, memo); return memo[n]; }这就是记忆化递归思路和自顶向下的动态规划是同一种东西。说这个例子是想提醒五人年龄这种线性递推其实是递归里最简单的一类它不需要记忆化一旦你在递归里发现同一个子问题被反复计算就该考虑加缓存。判断方法是画调用树看有没有重复的节点。不过这道题本身不需要这些初学者要是把这几个概念混在一起反而容易晕。先吃透最简单的再往复杂递推走。6. 这道题背后的递归气质真实开发里递归到底在解决什么6.1 树形结构遍历目录、菜单、组织架构都是递归的天下五人年龄每年看着像数学题但它训练出来的递归思维在真实项目里最常见的落脚点是树的遍历。比如你有一个菜单表菜单下面有子菜单子菜单下面还有子菜单要返回整棵菜单树最自然的写法就是递归public ListMenu buildTree(ListMenu allMenus, Long parentId) { ListMenu tree new ArrayList(); for (Menu menu : allMenus) { if (parentId.equals(menu.getParentId())) { menu.setChildren(buildTree(allMenus, menu.getId())); tree.add(menu); } } return tree; }这段代码和age(n)有一个共同点方法在处理一个问题时把子问题交给“同一个方法”去处理只是把范围缩小了。目录树的深度未知树的结构又天然是递归定义的——一个目录里包含一堆子目录所以递归写出来几乎不需要额外解释。你要是用循环去拼这棵树就得自己搞一个Map暂存节点、手动关联父子关系代码长度能翻好几倍还容易漏。这就是我前面说的问题定义是递归的就用递归。6.2 分治与回溯递归在算法题里的另外两副面孔如果把视野放大一点递归还撑起了两类经典算法。一类是分治比如归并排序把数组拆成两半分别排序再合并。每一半的排序方法完全一样。这里递归表达的是“问题规模的缩小”和年龄题一个套路。另一类是回溯比如八皇后、数独、全排列它们在一个决策空间里尝试一条路不行就回到上一个选择点换一条路。回溯的代码里经常出现这样的模式先做一个选择然后递归进入下一层递归返回后再撤销选择。核心难点不是递归本身而是如何管理状态。但如果你没有递归的底子这些算法连入口都找不到。所以五人年龄这道题虽然简单它给的是一种“看到规模n的问题敢不敢把它交给规模n-1的同样问题”的信心。这个思维方式迁移到分治、回溯、动态规划上都通用。6.3 面试讲到什么程度算“讲透”了这个题最后聊聊面试。如果被问到这道题背下来的答案是这样的if (n 1) return 10; return age(n - 1) 2;。但面试官真的只想听这两行吗我建议照这个顺序讲先说数学递推式age(1)10、age(n)age(n-1)2再写代码然后用手比划一下调用栈说age(5)压栈到age(1)再一层层弹栈把结果带回来最后主动补一句这个题递归深度很小没问题如果n很大我会用for循环或显式栈来避免栈溢出。这段话讲完面试官听到的不只是一个递归函数而是递推建模能力、对运行时原理的理解、以及工程取舍意识。这三样恰好是初级开发最常见的短板。我自己带新人时也喜欢用这道题先写循环再写递归的做法两个版本一对比栈的优势和代价就都出来了。比背十遍“递归就是函数调用自己”有用得多。写到这里突然想起来当年我也是先被这道题绕晕的人之一。后来把调用栈那张图画明白才真正觉得递归通了。说实话递归不是一种需要“背”的语法它是一种把问题缩小一层再解决的思维习惯。五人年龄只是最小的一个例子但它足够小小到你可以亲眼看见每一层栈帧的进出。把这道题彻底吃透再回头看更复杂的递归你会发现骨架都一样。最后分享一个小习惯无论写什么递归我先在注释里把递推公式和基准条件写出来再动手写代码。这个习惯帮我挡掉了至少一半的递归Bug。