JAVA递归算法实践：15个经典案例深入解析

在编程领域中，递归是一种常见的算法设计技巧，它允许一个函数调用自身来解决问题。Java语言因其面向对象的特性，特别适合实现递归算法。下面详细介绍标题中提到的15个典型的递归算法的Java实现及相关知识点。 ### 1. 求N的阶乘 阶乘是一个非负整数n的所有正整数乘积。递归实现阶乘通常基于这样一个事实：n! = n * (n-1)!。当n=0时，0!=1。 ```java public static long factorial(int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } ``` ### 2. 欧几里德算法（求最大公约数） 欧几里德算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。递归实现就是基于这个原理。 ```java public static int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } ``` ### 3. 斐波那契数列 斐波那契数列是一个每个数字是前两个数字之和的序列，通常以0和1开始。递归实现斐波那契数列需要两个前一个数作为参数。 ```java public static int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } ``` ### 4. 汉诺塔问题 汉诺塔问题涉及将一系列大小不同、穿孔的圆盘从一个塔座移动到另一个塔座，且在移动过程中大盘始终不能置于小盘之上。 ```java public static void hanoi(int n, String from, String aux, String to) { if (n == 1) { System.out.println("Move disk 1 from " + from + " to " + to); } else { hanoi(n - 1, from, to, aux); System.out.println("Move disk " + n + " from " + from + " to " + to); hanoi(n - 1, aux, from, to); } } ``` ### 5. 树的三种递归遍历方式 - 前序遍历（根-左-右） - 中序遍历（左-根-右） - 后序遍历（左-右-根） ```java public void traverse(Node node) { if (node == null) return; // 前序遍历 traverse(node.left); visit(node); // 访问当前节点 traverse(node.right); // 中序遍历 // traverse(node.left); // traverse(node.right); // visit(node); // 后序遍历 } ``` ### 6. 快速排序 快速排序是一种分治策略的排序算法。它通过一个划分操作将数据分为独立的两部分，使得其中一部分的所有数据都比另一部分的所有数据要小。 ```java public static void quickSort(int[] array, int low, int high) { if (low < high) { int pivot = partition(array, low, high); quickSort(array, low, pivot - 1); quickSort(array, pivot + 1, high); } } private static int partition(int[] array, int low, int high) { // ... } ``` ### 7. 折半查找 折半查找又称二分查找，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找。 ```java public static int binarySearch(int[] array, int target) { int low = 0; int high = array.length - 1; while (low <= high) { int mid = (low + high) / 2; int midVal = array[mid]; if (midVal < target) { low = mid + 1; } else if (midVal > target) { high = mid - 1; } else { return mid; // target found } } return -(low + 1); // target not found } ``` ### 8. 图的遍历 图的遍历通常使用深度优先搜索（DFS）和广度优先搜索（BFS），它们都可递归实现。 ```java // DFS的递归实现 public void dfs(Node node) { // visit(node); for (Node neighbor : node.getNeighbors()) { if (!visited[neighbor.id]) { visited[neighbor.id] = true; dfs(neighbor); } } } ``` ### 9. 归并排序 归并排序是一种分治算法，其思想是将数组分成两半，分别对它们进行排序，然后将结果合并起来。 ```java public static void mergeSort(int[] array, int[] temp, int leftStart, int rightEnd) { if (leftStart >= rightEnd) { return; } int middle = (leftStart + rightEnd) / 2; mergeSort(array, temp, leftStart, middle); mergeSort(array, temp, middle + 1, rightEnd); mergeHalves(array, temp, leftStart, rightEnd); } private static void mergeHalves(int[] array, int[] temp, int leftStart, int rightEnd) { // ... } ``` ### 10. 八皇后问题（回溯、递归） 八皇后问题要求在一个8x8的棋盘上放置8个皇后，使得它们互不攻击。通常使用回溯法解决，这涉及到递归。 ```java public void solveNQueens(int board[][], int row) { if (row >= board.length) { printSolution(board); return; } for (int i = 0; i < board.length; i++) { if (isSafe(board, row, i)) { board[row][i] = 1; solveNQueens(board, row + 1); board[row][i] = 0; } } } ``` ### 11. 棋盘覆盖（分治,递归） 棋盘覆盖问题是指给定一个2^n * 2^n的棋盘以及一个特殊的方格，要求用L型骨牌覆盖除了特殊方格以外的所有方格。 ```java public static void coverBoard(int tr, int tc, int dr, int dc, int n) { if (n == 0) return; int t = 1 << (n - 1); if (dr < tr + t) { if (dc < tc + t) { coverBoard(tr, tc, dr, dc, n - 1); } else { board[tr + t - 1][dc] = 1; coverBoard(tr, tc, dr, tc + t - 1, n - 1); board[tr + t - 1][dc] = 0; } } else if (dc < tc + t) { board[tr][tc + t - 1] = 1; coverBoard(tr, tc, tr + t - 1, dc, n - 1); board[tr][tc + t - 1] = 0; } else { board[tr + t - 1][tc + t - 1] = 1; coverBoard(tr, tc, tr + t - 1, tc + t - 1, n - 1); board[tr + t - 1][tc + t - 1] = 0; } } ``` ### 12. Strassen矩阵乘法（分治） Strassen算法是一种分治算法，用于矩阵乘法，它降低了乘法的递归复杂度。 ```java public static int[][] strassenMultiply(int[][] X, int[][] Y) { // ... } ``` ### 13. 最近点对问题(分治+递归) 最近点对问题是指在一个平面上给定n个点，找出距离最近的一对点。 ```java public static double closestPair(Point[] points) { // ... } ``` ### 14. 循环赛日程表 循环赛日程表是一种竞赛形式，其中每个参与者都与其他参与者进行一次比赛。递归方法可以用来生成日程表。 ```java // 递归实现略 ``` ### 15. 凸包问题求解 凸包是指在平面上的一组点形成的最小凸多边形，使得所有点都在这个多边形的边界上或内部。 ```java // 凸包求解略 ``` 对于树的遍历、图的遍历以及八皇后问题等，实际代码实现会更加复杂，因为需要处理更多的边界情况以及递归调用的细节。这些算法的学习和理解不仅有助于掌握递归这种编程技巧，同时也能够加深对分治和回溯等算法思想的理解，对提升算法和数据结构的能力有着重要意义。