java常见递归练习题-java教程-PHP中文网

java常见递归练习题

冷漠man

发布： 2025-12-03 15:46:49

原创

423人浏览过

阶乘：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编程中非常重要的一个概念，尤其在处理树形结构、分治算法和动态规划等问题时非常有用。掌握常见的递归练习题，有助于理解递归的执行机制和调用栈的工作方式。以下是几个经典的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. 数组元素求和

问题描述： 使用递归计算数组中所有元素的和。

Codeium

一个免费的AI代码自动完成和搜索工具

228

查看详情

实现方式： 将问题分解为“当前元素 + 剩余部分的和”。

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);
    }
}

登录后复制

说明： 先递归处理高位，再输出当前位，实现从左到右输出。

基本上就这些常见题目。理解每道题的递归终止条件和递推关系是关键。写递归时注意避免无限调用，确保参数向终止条件收敛。多练习能提升对调用栈和程序流程的理解。

以上就是java常见递归练习题的详细内容，更多请关注php中文网其它相关文章！