【算法基础】递归算法 - JAVA

一、递归基础

1.1 什么是递归算法

递归算法是一种通过函数调用自身来解决问题的方法。简单来说，就是"自己调用自己"。递归将复杂问题分解为同类的更简单子问题，直到达到易于直接解决的基本情况。

1.2 递归的核心要素

递归算法由两个关键部分组成：

• 边界条件（终止条件）：决定递归何时结束，避免无限递归
• 递归步骤：函数调用自身处理较小规模的问题

1.3 递归的基本结构

public ReturnType recursiveMethod(Parameters params) {// 边界条件（终止条件）if (结束条件) {return 结束值;}// 递归步骤return recursiveMethod(减小规模的参数);
}

1.4 递归的复杂度分析

时间复杂度：递归算法的时间复杂度主要取决于以下因素：

• 递归调用的次数
• 每次递归中的非递归操作耗时

递归算法的时间复杂度通常可以用递推关系表示：

• T(n) = a·T(n/b) + f(n)
  • T(n)是规模为n的问题的时间复杂度
  • a是每次递归调用的次数
  • n/b是子问题的规模
  • f(n)是除递归调用外的操作耗时

空间复杂度：递归算法的空间复杂度考虑两部分：

• 递归调用栈空间：与递归深度成正比
• 额外使用的数据结构空间

递归调用的栈空间通常是递归算法空间复杂度的主要部分，对于最大递归深度为D的算法，栈空间复杂度为O(D)。

二、简单递归示例

2.1 计算1到n的和

计算 1+2+3+...+n 的和是理解递归的最佳入门示例。

public class SumExample {public static void main(String[] args) {// 计算1到100的和System.out.println("1到100的和: " + getSum(100));}// 计算从1到n的和的递归方法public static int getSum(int n) {// 边界条件：当n为1时，直接返回1if (n == 1) {return 1;}// 递归步骤：n加上(n-1)的和return n + getSum(n - 1);}
}

递归执行过程详解

以计算getSum(5)为例，让我们看看递归的具体执行过程：

正向递归调用过程（自顶向下）：

1. 调用getSum(5)，因为5 != 1，执行return 5 + getSum(4)，暂停等待getSum(4)的结果
2. 调用getSum(4)，因为4 != 1，执行return 4 + getSum(3)，暂停等待getSum(3)的结果
3. 调用getSum(3)，因为3 != 1，执行return 3 + getSum(2)，暂停等待getSum(2)的结果
4. 调用getSum(2)，因为2 != 1，执行return 2 + getSum(1)，暂停等待getSum(1)的结果
5. 调用getSum(1)，满足边界条件n == 1，直接return 1

反向结果返回过程（自底向上）：

1. getSum(1)返回1
2. getSum(2)继续执行计算2 + 1 = 3，返回3
3. getSum(3)继续执行计算3 + 3 = 6，返回6
4. getSum(4)继续执行计算4 + 6 = 10，返回10
5. getSum(5)继续执行计算5 + 10 = 15，返回15，计算完成

可以看到，递归过程包含两个阶段：

• 分解阶段：将问题拆解为更小的子问题
• 回溯阶段：从最简单情况开始，逐层向上计算结果

2.2 计算阶乘

阶乘是另一个简单的递归实例。n的阶乘定义为：n! = n * (n-1) * (n-2) * ... * 2 * 1。

public class FactorialExample {public static void main(String[] args) {int n = 5;System.out.println(n + "的阶乘是: " + factorial(n));}// 计算阶乘的递归方法public static int factorial(int n) {// 边界条件if (n == 0 || n == 1) {return 1;}// 递归步骤return n * factorial(n - 1);}
}

递归执行过程

计算factorial(4)的步骤：

1. factorial(4) → 4 * factorial(3)
2. factorial(3) → 3 * factorial(2)
3. factorial(2) → 2 * factorial(1)
4. factorial(1) → 返回1（边界条件）
5. factorial(2) → 2 * 1 = 2
6. factorial(3) → 3 * 2 = 6
7. factorial(4) → 4 * 6 = 24

时间复杂度分析：

• 阶乘递归函数的调用次数与输入n成正比
• 每次函数调用中只有常数级别的操作
• 总时间复杂度：O(n)

空间复杂度分析：

• 递归深度为n，每层递归使用常数级别的空间
• 总空间复杂度：O(n)

2.3 斐波那契数列

斐波那契数列是一个经典递归案例，定义为：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)。

public class FibonacciExample {public static void main(String[] args) {int n = 7;System.out.println("斐波那契数列第" + n + "个数是: " + fibonacci(n));// 打印斐波那契数列的前10个数System.out.print("斐波那契数列前10个数: ");for (int i = 0; i < 10; i++) {System.out.print(fibonacci(i) + " ");}}// 计算斐波那契数列的递归方法public static int fibonacci(int n) {// 边界条件if (n == 0) {return 0;}if (n == 1) {return 1;}// 递归步骤return fibonacci(n - 1) + fibonacci(n - 2);}
}

特别注意

斐波那契数列的简单递归实现存在大量重复计算，效率较低。例如计算fibonacci(5)时，fibonacci(3)会被重复计算多次。这个问题在后面的优化部分会详细讨论。

时间复杂度分析：

• 未优化的递归斐波那契函数时间复杂度为O(2^n)
• 这是因为每个递归调用会产生两个新的递归调用，形成二叉树结构
• 树的高度为n，节点总数约为2^n-1

空间复杂度分析：

• 虽然会有大量函数调用，但递归栈的最大深度为n
• 空间复杂度：O(n)

三、理解递归思维

3.1 递归思维的要点

递归思维的核心是把大问题分解成小问题：

1. 相信函数能完成任务：假设对于较小规模的输入，函数已经能正确工作
2. 确保边界情况正确：解决最简单的情况作为起点
3. 确保递归逐步接近边界：每次递归，问题规模都应该变小

3.2 设计递归函数的步骤

1. 确定函数的功能和参数：明确函数要完成什么任务，需要哪些参数
2. 确定边界条件：找到最简单的情况，直接给出答案
3. 确定递归关系：将原问题分解为更小规模的子问题
4. 组合子问题结果：如何从子问题的解得到原问题的解

四、递归的实际应用

4.1 二分查找

二分查找是在有序数组中查找特定元素的高效算法，可以使用递归实现。

public class BinarySearchExample {public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};int target = 11;int result = binarySearch(arr, target, 0, arr.length - 1);if (result != -1) {System.out.println("元素 " + target + " 在索引 " + result + " 处");} else {System.out.println("元素 " + target + " 不在数组中");}}// 递归实现的二分查找public static int binarySearch(int[] arr, int target, int left, int right) {// 边界条件：如果查找范围无效，返回-1if (left > right) {return -1;}// 计算中间索引int mid = left + (right - left) / 2;// 找到目标，返回索引if (arr[mid] == target) {return mid;}// 根据中间值与目标值的比较，递归查找左半部分或右半部分if (arr[mid] > target) {return binarySearch(arr, target, left, mid - 1);} else {return binarySearch(arr, target, mid + 1, right);}}
}

递归过程分析

以查找值11为例：

1. binarySearch(arr, 11, 0, 9)，计算mid=4，arr[4]=9 < 11，递归调用右半部分
2. binarySearch(arr, 11, 5, 9)，计算mid=7，arr[7]=15 > 11，递归调用左半部分
3. binarySearch(arr, 11, 5, 6)，计算mid=5，arr[5]=11 == 11，返回5（找到）

时间复杂度分析：

• 每次递归调用将搜索范围减半
• 对于长度为n的数组，最多需要log₂n次递归调用
• 每次递归中的操作是常数级别的
• 总时间复杂度：O(log n)

空间复杂度分析：

• 递归深度最多为log₂n
• 每层递归使用常数级别的额外空间
• 总空间复杂度：O(log n)

4.2 求解全排列

全排列问题是递归的经典应用。给定一组不同的数字，求其所有可能的排列。

public class PermutationExample {public static void main(String[] args) {String str = "ABC";System.out.println("字符串\"" + str + "\"的全排列:");permute(str.toCharArray(), 0, str.length() - 1);}// 生成全排列的递归方法public static void permute(char[] arr, int start, int end) {// 边界条件：当只剩一个字符时，打印当前排列if (start == end) {System.out.println(String.valueOf(arr));return;}// 递归步骤：固定一个字符，对剩余字符进行全排列for (int i = start; i <= end; i++) {// 交换字符swap(arr, start, i);// 递归生成其余字符的排列permute(arr, start + 1, end);// 恢复原来的顺序（回溯）swap(arr, start, i);}}// 交换字符的辅助方法private static void swap(char[] arr, int i, int j) {char temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

递归思路解释

以字符串"ABC"为例：

1. 首先，我们固定第一个位置（索引0）的字符，然后对剩余字符递归生成全排列
   • 固定A：递归处理"BC"的排列
   • 固定B：递归处理"AC"的排列
   • 固定C：递归处理"AB"的排列
2. 当递归到只剩一个字符时，我们已经生成了一个完整的排列

时间复杂度分析：

• 对于长度为n的字符串，共有n!种排列
• 每生成一个排列需要O(n)的时间（打印或存储）
• 总时间复杂度：O(n × n!)

空间复杂度分析：

• 递归深度为n，每层递归使用常数级别的额外空间
• 如果考虑输出存储，需要O(n × n!)的空间
• 仅递归调用栈的空间复杂度：O(n)

4.3 汉诺塔问题

汉诺塔是递归的经典问题，它很好地展示了递归如何简化看似复杂的问题。

public class TowerOfHanoiExample {public static void main(String[] args) {int n = 3; // 盘子数量System.out.println("移动" + n + "个盘子的步骤:");moveDisks(n, 'A', 'B', 'C');}// 移动汉诺塔盘子的递归方法public static void moveDisks(int n, char source, char auxiliary, char target) {// 边界条件：只有一个盘子时，直接从起始柱移到目标柱if (n == 1) {System.out.println("将盘子1从" + source + "移动到" + target);return;}// 递归步骤1：将n-1个盘子从起始柱移到辅助柱moveDisks(n - 1, source, target, auxiliary);// 移动最大的盘子从起始柱到目标柱System.out.println("将盘子" + n + "从" + source + "移动到" + target);// 递归步骤2：将n-1个盘子从辅助柱移到目标柱moveDisks(n - 1, auxiliary, source, target);}
}

递归思路解释

汉诺塔问题的美妙之处在于利用递归，我们可以将复杂的多盘子问题，分解为更简单的子问题：

1. 将上面n-1个盘子从起始柱移到辅助柱
2. 将最底下的盘子从起始柱移到目标柱
3. 将辅助柱上的n-1个盘子移到目标柱

这里的关键是"相信"递归函数能够正确移动n-1个盘子，这样就能将复杂问题简化。

时间复杂度分析：

• 对于n个盘子，总共需要2^n-1步移动
• 每层递归产生两个新的递归调用，直到达到基本情况
• 总时间复杂度：O(2^n)

空间复杂度分析：

• 递归调用的最大深度为n
• 每层递归使用常数级别的额外空间
• 总空间复杂度：O(n)

五、递归优化技巧

5.1 记忆化递归（备忘录法）

斐波那契数列的简单递归实现效率很低，因为有大量重复计算。使用记忆化技术可以显著提高效率。

public class MemoizedFibonacci {public static void main(String[] args) {int n = 40;// 比较普通递归和记忆化递归的时间long startTime = System.currentTimeMillis();System.out.println("斐波那契(" + n + ") = " + fibonacciMemoized(n));long endTime = System.currentTimeMillis();System.out.println("记忆化递归耗时: " + (endTime - startTime) + "毫秒");}// 使用记忆化的斐波那契数列递归方法public static long fibonacciMemoized(int n) {// 创建备忘录数组，保存计算过的结果long[] memo = new long[n + 1];return fibHelper(n, memo);}private static long fibHelper(int n, long[] memo) {// 边界条件if (n <= 1) {return n;}// 如果已经计算过，直接返回结果if (memo[n] != 0) {return memo[n];}// 递归计算并保存结果memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);return memo[n];}
}

记忆化递归的关键思想：

• 用数组或HashMap存储已计算的值
• 每次函数调用前先检查是否已计算
• 只计算未知结果并保存

复杂度优化分析：

• 时间复杂度：从指数级O(2^n)降低到线性O(n)
  • 每个斐波那契数只计算一次
  • 总共计算n+1个数，每次计算是常数时间
• 空间复杂度：O(n)
  • 需要额外的长度为n+1的数组存储计算结果
  • 递归调用栈深度为O(n)

5.2 尾递归优化

尾递归是一种特殊的递归形式，它在函数返回时不做额外计算，直接返回递归调用的结果。这种形式更容易被编译器优化。

以阶乘计算为例：

public class TailRecursionExample {public static void main(String[] args) {int n = 5;System.out.println(n + "的阶乘: " + factorial(n));System.out.println(n + "的阶乘(尾递归): " + factorialTail(n, 1));}// 普通递归实现阶乘public static int factorial(int n) {if (n <= 1) {return 1;}return n * factorial(n - 1);  // 在递归调用后还需要乘以n}// 尾递归实现阶乘public static int factorialTail(int n, int result) {if (n <= 1) {return result;}return factorialTail(n - 1, n * result);  // 直接返回递归调用的结果}
}

尾递归的特点：

• 递归调用是函数的最后一个操作
• 递归调用的返回值直接作为函数的返回值
• 不需要额外的计算或状态保存

注意：虽然Java不会自动优化尾递归，但理解尾递归仍有助于编写更高效的代码，尤其是在支持尾递归优化的语言中。

5.3 避免重复计算

在一些递归算法中，避免重复计算是提高效率的关键。以下是几种常见技巧：

1. 使用缓存：与记忆化类似，保存中间结果
2. 参数传递：通过参数传递已计算的信息，避免重复计算
3. 状态记录：使用额外变量记录状态，避免重复检查

六、递归的常见陷阱与解决方法

6.1 无限递归

如果忘记设置正确的终止条件，或递归时参数未正确减小，可能导致无限递归，最终导致栈溢出。

解决方法：

• 确保每次递归都朝着终止条件推进
• 检查边界条件是否全面且正确
• 考虑添加最大递归深度限制

6.2 栈溢出

递归层数过多会导致栈溢出（StackOverflowError）。

解决方法：

• 优化递归算法，减少递归深度
• 将递归转换为迭代
• 使用尾递归优化（在支持的语言中）
• 增大JVM栈大小（-Xss参数）

6.3 重复递归调用

在某些算法中，同一参数的递归调用可能被多次执行，导致不必要的计算。

解决方法：

• 使用记忆化技术（备忘录模式）
• 优化算法结构，避免重复调用
• 考虑使用自底向上的迭代方法

七、递归转迭代

有时，递归算法可能面临效率或栈空间限制，此时可以考虑将递归转换为迭代。

7.1 斐波那契数列的迭代实现

public static long fibonacciIterative(int n) {if (n <= 1) {return n;}long fib = 0;long prev1 = 1;long prev2 = 0;for (int i = 2; i <= n; i++) {fib = prev1 + prev2;prev2 = prev1;prev1 = fib;}return fib;
}

复杂度分析：

• 时间复杂度：O(n) - 只需一次遍历
• 空间复杂度：O(1) - 只使用了常数个变量

7.2 阶乘的迭代实现

public static int factorialIterative(int n) {int result = 1;for (int i = 2; i <= n; i++) {result *= i;}return result;
}

复杂度分析：

• 时间复杂度：O(n) - 需要n-1次乘法运算
• 空间复杂度：O(1) - 只使用了常数个变量

递归转迭代的一般思路：

1. 使用栈或其他数据结构模拟递归过程
2. 找出算法中的状态变量
3. 通过循环代替递归调用
4. 手动管理状态变更

转换后的优势：

• 避免栈溢出风险
• 降低函数调用开销
• 通常具有更低的空间复杂度
• 在某些情况下可提高执行速度

八、总结

8.1 递归的核心要点

• 分而治之：将大问题分解为相似的小问题
• 边界条件：解决最基本情况的方法
• 递归关系：大问题与小问题之间的联系

8.2 何时使用递归

适合使用递归的情况：

• 问题可以自然地分解为相似的子问题
• 问题的规模会逐渐减小
• 数据结构具有递归性质（如树、图）
• 代码简洁度比极限性能更重要

不适合使用递归的情况：

• 递归深度可能非常大
• 对执行效率有严格要求
• 问题可以简单地用迭代解决

8.3 递归思维的价值

掌握递归思维不仅是掌握一种编程技巧，更是一种解决问题的思路：

• 学会将复杂问题分解
• 培养"相信函数能工作"的思维方式
• 理解如何从子问题构建完整解决方案

递归是算法设计中的强大工具，掌握它将帮助你解决许多看似复杂的问题。通过从简单例子开始，逐步理解递归的核心概念，再结合优化技巧，你将能够写出既高效又优雅的递归算法。