Java递归编程面试题及详细答案（高频实战）

Java递归编程面试题及详细答案（高频实战）本文整理互联网面试高频出现的Java递归编程题，涵盖入门基础、算法经典、数组链表实操题型，所有题目均附带解题思路+完整可运行代码+步骤解析，贴合真实面试手写代码场景，无冗余话术。递归核心必备知识点：递归本质是方法自身调用自身，必须满足两个核心条件：1、递归出口（终止条件，避免死循环栈溢出）；2、递归递推公式（问题拆分规则）。一、基础入门递归题（新手必问）题目1：递归实现n的阶乘题目描述：输入一个正整数n，通过递归方式计算n!（阶乘），阶乘定义：n!=1*2*3*...*n，0!和1!结果均为1。解题思路：1、递归出口：当n==0或n==1时，返回1；2、递推规则：n的阶乘=n*(n-1)的阶乘，即f(n)=n*f(n-1)；3、入参做合法性校验，避免负数输入报错。完整代码：java

publicclassRecursionDemo{

//递归计算阶乘

publicstaticintfactorial(intn){

//合法性校验

if(n<0){

thrownewIllegalArgumentException("输入数字不能为负数");

}

//递归出口

if(n==1||n==0){

return1;

}

//递推公式

returnn*factorial(n-1);

}

publicstaticvoidmain(String[]args){

System.out.println(factorial(5));//输出120

System.out.println(factorial(1));//输出1

System.out.println(factorial(6));//输出720

}

}详细解析：以n=5为例，执行流程：factorial(5)=5*factorial(4)factorial(4)=4*factorial(3)factorial(3)=3*factorial(2)factorial(2)=2*factorial(1)factorial(1)=1（触发出口）逐层回溯计算：2*1=2、3*2=6、4*6=24、5*24=120，最终得出结果。题目2：递归实现1~n累加求和题目描述：输入正整数n，递归计算1+2+3+...+n的和。解题思路：1、递归出口：n=1时，和为1；2、递推规则：f(n)=n+f(n-1)，将n的累加拆分为当前数+前n-1个数的和。完整代码：java

publicclassRecursionSum{

publicstaticintsum(intn){

if(n<1){

thrownewIllegalArgumentException("请输入正整数");

}

if(n==1){

return1;

}

returnn+sum(n-1);

}

publicstaticvoidmain(String[]args){

System.out.println(sum(10));//输出55

System.out.println(sum(5));//输出15

}

}解析：n=10时，不断拆分，直到n=1触发出口，逐层回溯累加，最终得到1到10的总和。二、经典算法递归题（面试高频）题目3：递归实现斐波那契数列题目描述：斐波那契数列规则：第1项为1，第2项为1，从第3项开始，每一项等于前两项之和。即：1、1、2、3、5、8、13...，输入n，输出第n项数值。解题思路：1、递归出口：n=1或n=2时，返回1；2、递推规则：f(n)=f(n-1)+f(n-2)。完整代码：java

publicclassFibonacci{

publicstaticintfib(intn){

if(n<1){

thrownewIllegalArgumentException("输入必须为正整数");

}

//递归出口

if(n==1||n==2){

return1;

}

//递推公式

returnfib(n-1)+fib(n-2);

}

publicstaticvoidmain(String[]args){

System.out.println(fib(6));//输出8

System.out.println(fib(7));//输出13

}

}面试补充解析：该递归写法逻辑简单，但存在大量重复计算，时间复杂度O(2ⁿ)，n较大时会效率极低、栈溢出。面试中可主动提及优化方案：记忆化递归、迭代、动态规划。题目4：递归反转字符串题目描述：输入任意字符串，通过递归方式实现字符串反转，不使用reverse工具方法。解题思路：1、递归出口：字符串长度为0或1时，直接返回原字符串；2、递推规则：最后一个字符+剩余字符串的反转结果。完整代码：java

publicclassReverseStr{

publicstaticStringreverse(Stringstr){

//出口：空字符串或单个字符，无需反转

if(str==null||str.length()<=1){

returnstr;

}

//取最后一位+前面字符串递归反转

returnstr.charAt(str.length()-1)+reverse(str.substring(0,str.length()-1));

}

publicstaticvoidmain(String[]args){

System.out.println(reverse("abcdef"));//输出fedcba

System.out.println(reverse("123456"));//输出654321

}

}执行解析：以abc为例，执行流程：reverse("abc")='c'+reverse("ab")reverse("ab")='b'+reverse("a")reverse("a")="a"回溯结果：b+a=ba，最终c+ba=cba。三、进阶实操递归题（中高级面试）题目5：递归遍历数组求和题目描述：给定一个int数组，通过递归方式计算数组所有元素的总和，不使用for/while循环。解题思路：1、递归出口：数组遍历索引超出最大下标，返回0；2、递推规则：当前索引元素+后续所有元素的递归求和结果。完整代码：java

publicclassArraySum{

//递归数组求和，index为当前遍历的索引

publicstaticintgetArraySum(int[]arr,intindex){

//出口：索引超出数组长度，终止

if(index==arr.length){

return0;

}

//当前元素+后续元素求和

returnarr[index]+getArraySum(arr,index+1);

}

publicstaticvoidmain(String[]args){

int[]arr={1,2,3,4,5,6};

System.out.println(getArraySum(arr,0));//输出21

}

}解析：从索引0开始，每次累加当前元素，索引+1递归，直到遍历完整个数组，逐层回溯累加得到总和。题目6：递归求最大公约数（辗转相除法）题目描述：输入两个正整数，用递归实现欧几里得算法，计算最大公约数。算法规则：两个数的最大公约数=较小数和两数取余结果的最大公约数，余数为0时，当前较小数就是最大公约数。完整代码：java

publicclassGCD{

publicstaticintgcd(inta,intb){

//保证a、b为正数

a=Math.abs(a);

b=Math.abs(b);

//递归出口：余数为0，当前a为最大公约数

if(b==0){

returna;

}

//递推：用b和a%b继续递归

returngcd(b,a%b);

}

publicstaticvoidmain(String[]args){

System.out.println(gcd(24,18));//输出6

System.out.println(gcd(15,10));//输出5

}

}执行解析：以24和18为例：gc