递归算法（Recursion Algorithm）是一种重要的编程方法，核心思想是函数通过调用自身来解决问题。在递归中，一个复杂的问题被分解为相同类型但规模更小的子问题，直到达到一个简单到可以直接解决的基本情况（基准情况）。递归算法特别适合解决具有自相似结构的问题，时间复杂度跟递归深度和每层处理的复杂度有关。
递归算法的妙处在于它能用简洁优雅的代码解决看似复杂的问题，但在使用时一定要注意避免无限递归和重复计算等问题。
核心特性：
接下来通过阶乘（factorial）计算来展示递归算法的实现：
public class Factorial {
public static int factorial(int n) {
// 基准情况
if (n == 0 || n == 1) {
return 1;
}
// 递归情况：n! = n * (n-1)!
return n * factorial(n - 1);
}
// 测试
public static void main(String[] args) {
for (int i = 0; i 实现递归的核心思想，将计算 n! 的问题转化为计算 (n-1)! 的子问题。同时设置清晰的终止条件 if (n == 0 || n == 1) return 1; 确保递归能够结束。
通过将递归操作放在函数返回位置，可以被编译器优化，避免额外的栈空间消耗
public static int factorialTailRecursive(int n) {
return factorialHelper(n, 1);
}
private static int factorialHelper(int n, int accumulator) {
// 基准情况
if (n == 0 || n == 1) {
return accumulator;
}
// 尾递归调用
return factorialHelper(n - 1, n * accumulator);
}
缓存已计算结果，避免重复计算
public static int factorialMemoization(int n) {
int[] memo = new int[n + 1];
return factorialWithMemo(n, memo);
}
private static int factorialWithMemo(int n, int[] memo) {
// 基准情况
if (n == 0 || n == 1) {
return 1;
}
// 检查是否已计算
if (memo[n] != 0) {
return memo[n];
}
// 计算并缓存结果
memo[n] = n * factorialWithMemo(n - 1, memo);
return memo[n];
}
1）数学计算：阶乘、斐波那契数列、组合数等
2）数据结构操作：树的遍历、图的搜索（DFS）
3）分治算法：归并排序、快速排序
4）动态规划：子问题的递归求解
5）回溯算法：排列组合、八皇后、数独求解
给大家推荐一些可以用来练手的 LeetCode 题目：
分治法(Divide and Conquer)是一种解决复杂问题的重要算法思想，其核心思想是将一个难以直接解决的大问题，分割成若干个规模较小的子问题，以便各个击破，最后将子问题的解组合起来，得到原问题的解。分治法的思想可以追溯到古代，但作为一种系统化的算法策略，它在计算机科学领域得到了极大的发展和应用。
分治算法通常遵循以下三个步骤：
核心特性：
本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top
登录查看全部
参与评论
手机查看
返回顶部