递归函数的基本概念
递归函数是一种在函数体内调用自身的函数，通过将复杂问题分解为更小的同类子问题来求解，在Java中，递归通常需要满足两个核心条件：基准条件（终止条件）和递归条件，基准条件用于终止递归，避免无限循环；递归条件则将问题分解为更小的子问题，并调用自身处理，递归在树结构遍历、分治算法、动态规划等领域有广泛应用，但其使用需谨慎,避免栈溢出或性能问题。
递归函数的执行原理
递归函数的执行依赖于Java的调用栈（Call Stack），每次调用函数时，系统会将函数的参数、局部变量和返回地址压入栈帧；当函数返回时，栈帧弹出，递归的本质是多次压栈和出栈的过程，计算阶乘的递归函数factorial(n)会依次调用factorial(n-1)、factorial(n-2)……直到factorial(1)（基准条件），然后逐层返回结果。
调用栈的深度受限于JVM的栈大小（通常为1MB左右），若递归深度过大（如计算factorial(10000)），会导致栈溢出错误（StackOverflowError），递归更适合问题规模可控的场景,或通过尾递归优化等技术规避风险。
递归函数的实现步骤
定义基准条件
基准条件是递归的出口，必须明确且可达成，计算阶乘时，n == 0或n == 1是基准条件，直接返回1；否则进入递归逻辑，若无基准条件，递归将无限进行，最终栈溢出。
分解问题并递归调用
将原问题分解为规模更小的子问题，并通过递归函数调用自身处理子问题，斐波那契数列的递归实现中，fib(n) = fib(n-1) + fib(n-2)，子问题规模每次减1或2，最终逼近基准条件fib(1) = 1和fib(0) = 0。
返回结果并合并
递归函数需逐层返回子问题的结果，并合并为最终结果，阶乘函数中，factorial(n) = n * factorial(n-1)，每次递归返回后，将子结果乘以当前n,最终得到完整结果。
递归函数的示例代码
示例1：计算阶乘
public static int factorial(int n) {
// 基准条件
if (n == 0 || n == 1) {
return 1;
}
// 递归条件
return n * factorial(n - 1);
}
调用factorial(5)的执行流程：
factorial(5)→ 调用factorial(4)factorial(4)→ 调用factorial(3)factorial(1)→ 返回1- 逐层返回：
2*1=2→3*2=6→4*6=24→5*24=120
示例2：斐波那契数列
public static int fibonacci(int n) {
// 基准条件
if (n <= 1) {
return n;
}
// 递归条件
return fibonacci(n - 1) + fibonacci(n - 2);
}
斐波那契递归存在重复计算问题（如fibonacci(4)会重复计算fibonacci(2)），可通过记忆化（Memoization）优化,存储已计算结果避免重复调用。
递归的优化与注意事项
尾递归优化
尾递归指递归调用是函数的最后一步操作，JVM目前未完全支持尾递归优化，但可通过循环或迭代替代尾递归，避免栈溢出，阶乘的尾递归实现：
public static int tailFactorial(int n, int accumulator) {
if (n == 0 || n == 1) {
return accumulator;
}
return tailFactorial(n - 1, n * accumulator); // 递归调用是最后一步
}
调用时通过tailFactorial(5, 1)启动，每次调用直接更新accumulator，无需保存中间栈帧。
避免重复计算
递归可能导致重复计算（如斐波那契数列），可通过记忆化或动态规划优化，使用数组存储已计算结果：
public static int memoizedFibonacci(int n, int[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] != 0) { // 已计算则直接返回
return memo[n];
}
memo[n] = memoizedFibonacci(n - 1, memo) + memoizedFibonacci(n - 2, memo);
return memo[n];
}
控制递归深度
对于大规模问题（如深度优先遍历深度过大的树），可改用迭代+栈模拟递归，避免栈溢出，通过Stack类实现树的深度优先遍历：
public void iterativeDFS(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
递归函数是解决复杂问题的强大工具，但需合理设计基准条件、控制递归深度，并通过优化技术（如记忆化、尾递归）提升性能，在实际开发中，需权衡递归的可读性与性能，优先选择迭代或动态规划等更高效的方法处理大规模数据，掌握递归的核心原理与优化技巧，能帮助开发者更优雅地解决分治、树遍历等经典问题。
