09-递归

递归是一种强大的编程技术，通过函数直接或间接调用自身来解决问题。它特别适用于可以分解为相似子问题的情况，如链表遍历、阶乘计算、字符串反转等。以下是递归的核心要点和经典应用示例：

递归的核心要点

基本情况（Base Case）递归必须有一个明确的终止条件，避免无限递归。例如：
链表遍历中，当节点为 null 时停止。
阶乘计算中，0! = 1 或 1! = 1。
递推关系将问题分解为更小的子问题。例如：
阶乘：n! = n * (n-1)!
链表遍历：先处理当前节点，再递归处理 next 节点。
调用栈与“归”的过程递归通过调用栈保存状态，子问题解决后“归”回父问题。例如：
链表遍历中，先递归到链表末尾，再逐层返回打印节点值。

经典递归示例1. 链表递归遍历private void recursion(Node p) { if (p == null) return; // 基本情况 System.out.println("before: " + p.value); recursion(p.next); // 递归调用 System.out.println("after: " + p.value); // 归的过程}

输出逻辑：

递：从 head 开始，依次递归到链表末尾（null）。
归：从末尾返回，逐层打印节点值（后序遍历）。

2. 阶乘计算public static int fac(int n) { if (n == 0) return 1; // 基本情况 return n * fac(n - 1); // 递推关系}

执行过程：

fac(3) → 3 * fac(2) → 3 * 2 * fac(1) → 3 * 2 * 1 * fac(0) → 3 * 2 * 1 * 1 = 6。

3. 字符串反向打印public static void reversePrint(int n, String str) { if (n == str.length()) return; // 基本情况 reversePrint(n + 1, str); // 递归到末尾 System.out.print(str.charAt(n)); // 归时打印字符}

输出结果：输入 "abcde"，输出 "edcba"。

4. 二分查找（单路递归）public static int binarySearch(int[] a, int target, int i, int j) { if (i > j) return -1; // 未找到 int m = (i + j) >>> 1; // 计算中点 if (target < a[m]) return binarySearch(a, target, i, m - 1); // 左半部分 else if (target > a[m]) return binarySearch(a, target, m + 1, j); // 右半部分 else return m; // 找到目标}

关键点：每次递归将搜索范围缩小一半，直到找到目标或范围为空。

5. 冒泡排序（递归实现）private static void bubble(int[] a, int j) { if (j == 0) return; // 基本情况：已排序完成 for (int i = 0; i < j; i++) { // 一次冒泡 if (a[i] > a[i + 1]) swap(a, i, i + 1); } bubble(a, j - 1); // 递归处理剩余部分}

逻辑：每次递归将最大值“冒泡”到末尾，范围逐渐缩小。

6. 插入排序（递归实现）private static void insertion(int[] a, int low) { if (low == a.length) return; // 基本情况：全部插入完成 int v = a[low], j = low - 1; while (j >= 0 && v < a[j]) { // 找到插入位置 a[j + 1] = a[j]; j--; } a[j + 1] = v; // 插入值 insertion(a, low + 1); // 递归处理下一个元素}

逻辑：将当前元素插入已排序部分的正确位置，逐步构建有序数组。

递归的优缺点

优点：
代码简洁，易于理解（如树形结构、分治算法）。
自然匹配数学归纳法问题（如阶乘、斐波那契数列）。
缺点：
性能开销：递归调用消耗栈空间，可能导致栈溢出。
重复计算：未优化时（如朴素斐波那契递归）效率低。
调试复杂：需跟踪多层调用栈。

总结

递归通过分解问题为子问题简化代码，但需谨慎设计基本情况和递推关系。经典应用包括链表遍历、排序算法、搜索等。理解递归的“递”与“归”过程是掌握该技术的关键。

您可能感兴趣问答

Collapsible

热门标签

热点问答