阶乘：n! = n × (n-1)!，终止条件n=0或1；2. 斐波那契：f(n)=f(n-1)+f(n-2)，f(0)=0，f(1)=1；3. 最大公约数：gcd(a,b)=gcd(b,a%b)，b=0时返回a；4. 数组求和：当前元素+剩余元素和，索引达长度时终止；5. 字符串反转：首字符放至剩余字符串反转后结果末尾；6. 二分查找：递归在有序数组中找目标值，通过比较中间值缩小范围；7. 打印数字位：先递归处理高位，再打印当前位。
递归是Java编程中非常重要的一个概念，尤其在处理树形结构、分治算法和动态规划等问题时非常有用。掌握常见的递归练习题，有助于理解递归的执行机制和调用栈的工作方式。以下是几个经典的Java递归练习题及其解析。
1. 计算阶乘（Factorial）
问题描述： 编写一个递归方法，计算给定正整数n的阶乘（n!）。
思路： n的阶乘定义为 n * (n-1)!，当n=0或1时，阶乘为1。
public static long factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
注意： 输入值不宜过大，避免栈溢出或数值溢出。
立即学习“Java免费学习笔记（深入）”；
2. 斐波那契数列（Fibonacci）
问题描述： 使用递归求斐波那契数列的第n项，其中F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。
public static int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
说明： 此方法时间复杂度高（O(2^n)），适合理解递归，但不适合大数值计算。可使用记忆化优化。
3. 求两个数的最大公约数（GCD）
问题描述： 使用欧几里得算法，通过递归求两个整数的最大公约数。
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
提示： 利用“gcd(a, b) = gcd(b, a mod b)”的性质，递归终止条件是b为0。
4. 数组元素求和
问题描述： 使用递归计算数组中所有元素的和。
实现方式： 将问题分解为“当前元素 + 剩余部分的和”。
public static int sumArray(int[] arr, int index) {
if (index == arr.length) {
return 0;
}
return arr[index] + sumArray(arr, index + 1);
}
调用示例： sumArray(arr, 0) 从索引0开始累加。
5. 字符串反转
问题描述： 使用递归反转一个字符串。
public static String reverseString(String str) {
if (str.isEmpty()) {
return str;
}
return reverseString(str.substring(1)) + str.charAt(0);
}
逻辑： 每次取出第一个字符，放在剩余字符串反转后的结果后面。
6. 二分查找的递归实现
问题描述： 在有序数组中使用递归实现二分查找。
public static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) {
return -1; // 未找到
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
调用方式： binarySearch(arr, 0, arr.length - 1, target)
7. 打印数字的每一位（从高位到低位）
问题描述： 使用递归按顺序打印一个正整数的每一位数字。
public static void printDigits(int n) {
if (n < 10) {
System.out.println(n);
} else {
printDigits(n / 10);
System.out.println(n % 10);
}
}
说明： 先递归处理高位，再输出当前位，实现从左到右输出。
基本上就这些常见题目。理解每道题的递归终止条件和递推关系是关键。写递归时注意避免无限调用，确保参数向终止条件收敛。多练习能提升对调用栈和程序流程的理解。
