Java递归算法面试题及详细答案（实战面试版）

Java递归算法面试题及详细答案（实战面试版）本次题库筛选互联网大厂、中小厂高频递归面试题，从基础入门到进阶实战，贴合真实面试提问逻辑。所有题目均包含解题思路、递归终止条件、完整可运行代码、面试标准答案，无冗余话术，适合面试背诵、手撕代码复盘。递归核心面试核心要点（必背）：

1.递归三要素：终止条件、递归公式、参数传递

2.核心思想：把大问题拆解为相同逻辑的子问题

3.面试重点考察：会不会写终止条件、是否栈溢出、时间/空间复杂度一、基础递归面试题（入门必考）题目1：递归实现斐波那契数列题目描述：已知斐波那契数列规则：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3），通过递归输入n，返回第n项数值。解题思路：

1.终止条件：n=1、n=2时，直接返回1

2.递归逻辑：当前项等于前两项之和，不断拆解子问题

3.缺点：纯递归存在大量重复计算，n过大易栈溢出（面试需主动说出优缺点）java

publicclassRecursionDemo{

//递归实现斐波那契数列

publicstaticintfib(intn){

//递归终止条件

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

return1;

}

//递归公式

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

}

publicstaticvoidmain(String[]args){

//测试：输出第10项

System.out.println(fib(10));//结果：55

}

}面试标准答案：

斐波那契递归核心是拆分递推公式，临界值为前两项1。纯递归时间复杂度O(2ⁿ)，空间复杂度O(n)，存在大量重复递归计算，实际开发一般用迭代或动态规划优化，递归仅用于考察递归逻辑掌握程度。题目2：递归实现阶乘计算题目描述：输入正整数n，递归计算n的阶乘（n!=1*2*3*...*n，0!和1!均为1）。解题思路：

1.终止条件：n=0或n=1，返回1

2.递归逻辑：n!=n*(n-1)!，逐层向下拆解，触底后回溯计算结果java

publicclassRecursionDemo{

//递归求阶乘

publicstaticintfactorial(intn){

//合法性校验+终止条件

if(n<0){

thrownewIllegalArgumentException("负数没有阶乘");

}

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

return1;

}

returnn*factorial(n-1);

}

publicstaticvoidmain(String[]args){

System.out.println(factorial(5));//结果：120

}

}面试标准答案：

阶乘是最基础的线性递归，单次递归仅产生一个子问题，无重复计算。时间复杂度O(n)，空间复杂度O(n)，递归深度等于n，n过大会触发栈溢出异常。题目3：递归反转字符串题目描述：不使用自带反转API，通过递归实现字符串反转，输入abc，输出cba。解题思路：

1.终止条件：字符串长度≤1，直接返回原字符串

2.递归逻辑：最后一位字符+剩余字符串递归反转结果java

publicclassRecursionDemo{

//递归反转字符串

publicstaticStringreverseStr(Stringstr){

//终止条件：空字符串或单个字符，无需反转

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

returnstr;

}

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

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

}

publicstaticvoidmain(String[]args){

System.out.println(reverseStr("hello"));//结果：olleh

}

}面试标准答案：

字符串反转递归核心是拆分尾部字符，逐层截取子串递归处理。逻辑简单，主要考察递归拆解问题的思维，时间复杂度O(n)，空间复杂度O(n)。二、中频递归面试题（数组/链表场景）题目4：递归求数组最大值题目描述：给定整型数组，通过递归方式查找数组中的最大值，不使用循环遍历。解题思路：

1.终止条件：数组只剩一个元素，直接返回该元素

2.递归逻辑：首位元素和剩余数组的最大值对比，返回较大值java

publicclassRecursionDemo{

//递归求数组最大值

publicstaticintgetMax(int[]arr,intindex){

//终止条件：遍历到最后一个元素

if(index==arr.length-1){

returnarr[index];

}

//递归获取后续数组最大值，和当前值对比

returnMath.max(arr[index],getMax(arr,index+1));

}

publicstaticvoidmain(String[]args){

int[]arr={2,9,5,1,8,3};

System.out.println(getMax(arr,0));//结果：9

}

}面试标准答案：

通过索引递增实现数组递归遍历，每次递归处理当前元素与后续子数组的最值对比。时间复杂度O(n)，空间复杂度O(n)，适合考察递归遍历思维。题目5：递归实现链表反转（面试高频）题目描述：给定单链表，通过递归方式反转整个链表，返回反转后的头节点。解题思路：

1.终止条件：节点为空或只有一个节点，直接返回当前节点

2.递归逻辑：先递归反转后续链表，回溯时将当前节点的下一个节点指向自己，断开原指向java

//定义链表节点

classListNode{

intval;

ListNodenext;

ListNode(intval){

this.val=val;

}

}

publicclassRecursionDemo{

//递归反转链表

publicstaticListNodereverseList(ListNodehead){

//终止条件：空节点/尾节点

if(head==null||head.next==null){

returnhead;

}

//递归反转后续链表，newHead是反转后的新头节点

ListNodenewHead=reverseList(head.next);

//回溯修改指针：下一个节点指向当前节点

head.next.next=head;

//断开原指针，防止循环链表

head.next=null;

returnnewHead;

}

//遍历打印链表

publicstaticvoidprintList(ListNodehead){

while(head!=null){

System.out.print(head.val+"");

head=head.next;

}

}

publicstaticvoidmain(String[]args){

//构建链表1->2->3->4->5

ListNoden1=newListNode(1);

ListNoden2=newListNode(2);

ListNoden3=newListNode(3);

n1.next=n2;

n2.next=n3;

ListNodenewHead=reverseList(n1);

printList(newHead);//结果：321

}

}面试标准答案：

链表递归反转采用后序递归，先走到链表尾部，再回溯修改指针指向。核心难点是理解回溯过程的指针翻转，时间复杂度O(n)，空间复杂度O(n)，是链表核心面试考点。三、高频压轴递归面试题（算法进阶）题目6：递归实现二分查找题目描述：有序数组中，通过递归二分查找目标值，返回目标值索引，不存在则返回-1。解题思路：

1.终止条件：左边界>右边界，说明无目标值，返回-1

2.递归逻辑：取中间值，匹配成功返回索引；小于中间值递归查左区间，大于则递归查右区间java

publicclassRecursionDemo{

//递归二分查找

publicstaticintbinarySearch(int[]arr,intleft,intright,inttarget){

//终止条件：查找区间为空

if(left>right){

return-1;

}

//计算中间索引（避免溢出）

intmid=left+(right-left)/2;

if(arr[mid]==target){

returnmid;

}elseif(arr[mid]>target){

//目标更小，查找左区间

returnbinarySearch(arr,left,mid-1,target);

}else{

//目标更大，查找右区间

returnbinarySearch(arr,mid+1,right,target);

}

}

publicstaticvoidmain(String[]args){

int[]arr={1,3,5,7,9,11};

System.out.println(binarySearch(arr,0,arr.length-1,7));//结果：3

}

}面试标准答案：

递归二分查找核心是区间拆分，每次递归缩小一半查找范围。时间复杂度O(logn)，空间复杂度O(logn)，相比迭代版，递归代码更简洁但占用栈空间更多。题目7：递归求二叉树最大深度（LeetCode104原题）题目描述：给定二叉树根节点，求二叉树的最大深度（根节点到最远叶子节点的最长路径节点数）。解题思路：

1.终止条件：节点为空，深度为0

2.递归逻辑：当前节点深度=左右子树最大深度+1java

//定义二叉树节点

classTreeNode{

intval;

TreeNodeleft;

TreeNoderight;

TreeNode(intval){

this.val=val;

}

}

publicclassRecursionDemo{

//递归求二叉树最大深度

publicstaticintmaxDepth(TreeNoderoot){

//终止条件：空节点深度为0

if(root==null){

return0;

}

//递归计算左右子树深度

intleftDepth=maxDepth(root.left);

intrightDepth=maxDepth(root.right);

//当前节点最大深度=子树最大深度+1

returnMath.max(leftDepth,rightDepth)+1;

}

publicstaticvoidmain(String[]args){

//构建二叉树

TreeNode