概述为什么很多算法都离不开递归学完链表之后我们进入一个非常重要的算法思想递归。递归不是某一种具体的数据结构也不是某一道题的固定技巧。它更像是一种解决问题的思维方式把一个大问题拆成一个或多个结构相同的小问题比如求n!可以先求(n - 1)!反转链表可以先反转后面的链表遍历树可以先遍历左子树和右子树回溯搜索可以先处理当前选择再递归处理后续选择动态规划中的状态转移本质上也常常来自递归关系很多初学者觉得递归难主要不是因为代码长而是因为递归执行过程不像循环那样直观。循环是一步一步往前走递归则会不断进入新的函数调用再一层一层返回。这篇文章会从最基础的函数调用开始讲清楚什么是递归递归为什么必须有终止条件递归调用栈是怎么工作的如何写出递归代码递归的常见题型和坑点学完这篇你应该能看懂递归函数的执行过程并能根据“函数定义、终止条件、递推关系”写出基础递归代码。核心概念递归到底是什么递归就是函数在执行过程中调用自己。最简单的形式如下voidfunc(){func();}不过这段代码是错误示范。因为它会无限调用自己永远停不下来最后导致栈溢出。一个正确的递归函数通常长这样voidfunc(intn){if(n0){return;}func(n-1);}这里有两个关键点func(n - 1)把问题规模变小if (n 0)当问题足够小时停止递归递归的本质可以理解成当前问题 当前这一层要做的事 更小规模的同类问题比如求1 2 3 ... nsum(n) n sum(n - 1) sum(1) 1这就是递归关系。递归不是重复写代码而是让函数把问题交给规模更小的自己来解决。递归三要素写递归前先想清楚这三件事写递归时不建议一上来就写代码。更好的方式是先回答三个问题。1. 函数定义是什么也就是这个函数到底要解决什么问题。例如intsum(intn)可以定义为返回 1 到 n 的整数和这个定义非常重要。递归代码能不能写清楚很大程度取决于函数定义是否清楚。2. 终止条件是什么递归必须能停下来。对于sum(n)来说最小问题是sum(1) 1所以终止条件可以写成if(n1){return1;}如果没有终止条件递归会一直调用下去最终出现StackOverflowError。3. 递推关系是什么递推关系就是大问题和小问题之间的关系。对于sum(n)sum(n) n sum(n - 1)对应代码returnnsum(n-1);三个要素合在一起就是完整递归代码intsum(intn){if(n1){return1;}returnnsum(n-1);}递归三要素总结要素要回答的问题示例函数定义这个函数返回什么sum(n)返回1到n的和终止条件什么时候不用继续递归n 1递推关系大问题如何拆成小问题sum(n) n sum(n - 1)先定义函数含义再确定最小问题最后写出大问题和小问题的关系。调用栈递归代码到底是怎么执行的很多人看递归时容易迷糊是因为只看到了代码没有看到函数调用栈。以这段代码为例intsum(intn){if(n1){return1;}returnnsum(n-1);}调用sum(4)执行过程可以分成两个阶段不断向下递归调用到达终止条件后逐层返回调用展开过程sum(4) 4 sum(3) 3 sum(2) 2 sum(1) 1返回过程sum(1) 1 sum(2) 2 1 3 sum(3) 3 3 6 sum(4) 4 6 10如果画成调用栈可以这样理解入栈 sum(4) sum(3) sum(2) sum(1) 出栈 sum(1) 返回 1 sum(2) 返回 3 sum(3) 返回 6 sum(4) 返回 10每一次函数调用系统都会保存当前函数的局部变量、参数和执行位置。这些信息会放到调用栈中。所以递归虽然代码看起来短但它不是没有空间开销。递归层数越深占用的栈空间越多。递归会先不断压栈进入更小问题再从最小问题开始逐层返回答案。例题一计算阶乘题目给定正整数n计算n!。阶乘定义n! n * (n - 1) * (n - 2) * ... * 1例如5! 5 * 4 * 3 * 2 * 1 120解题思路先写函数定义factorial(n) 表示 n 的阶乘终止条件factorial(1) 1递推关系factorial(n) n * factorial(n - 1)Java 代码实现classSolution{publicintfactorial(intn){if(n1){return1;}returnn*factorial(n-1);}}执行过程以factorial(5)为例factorial(5) 5 * factorial(4) 5 * 4 * factorial(3) 5 * 4 * 3 * factorial(2) 5 * 4 * 3 * 2 * factorial(1) 5 * 4 * 3 * 2 * 1 120复杂度分析时间复杂度O(n)从n递归到1空间复杂度O(n)递归调用栈最多有n层例题二数组递归求和题目给定数组nums和下标index递归计算从index到数组末尾的元素和。示例nums [1, 2, 3, 4] sum(nums, 0) 10 sum(nums, 2) 7解题思路函数定义sum(nums, index) 表示 nums[index] 到 nums[nums.length - 1] 的元素和终止条件index nums.length当index已经越过最后一个元素时后面没有元素了返回0。递推关系sum(nums, index) nums[index] sum(nums, index 1)Java 代码实现classSolution{publicintsum(int[]nums,intindex){if(indexnums.length){return0;}returnnums[index]sum(nums,index1);}}为什么终止条件是index nums.length假设数组长度为4合法下标是0, 1, 2, 3当index 4时说明已经没有元素可加了。此时返回0不会影响前面的加法结果。复杂度分析时间复杂度O(n)每个元素处理一次空间复杂度O(n)递归深度最多为数组长度当前结果等于当前元素加上后面所有元素的和。例题三反转字符串题目给定字符数组s请原地反转这个字符数组。示例输入[h, e, l, l, o] 输出[o, l, l, e, h]这道题可以用双指针也可以用递归。递归写法本质上仍然是在模拟左右指针。解题思路定义递归函数reverse(s, left, right) 表示反转 s[left...right] 这一段终止条件left right当左指针和右指针相遇或交错说明反转完成。每一层递归做两件事交换s[left]和s[right]递归反转内部区间s[left 1...right - 1]Java 代码实现classSolution{publicvoidreverseString(char[]s){reverse(s,0,s.length-1);}privatevoidreverse(char[]s,intleft,intright){if(leftright){return;}chartemps[left];s[left]s[right];s[right]temp;reverse(s,left1,right-1);}}执行过程以[a, b, c, d]为例reverse(0, 3)交换 a 和 d - d b c a reverse(1, 2)交换 b 和 c - d c b a reverse(2, 1)left right结束复杂度分析时间复杂度O(n)每个字符最多交换一次空间复杂度O(n)递归调用栈最多约n / 2层如果只考虑最优空间双指针迭代写法可以做到O(1)额外空间。这也说明递归虽然优雅但不一定总是空间最优。例题四斐波那契数列斐波那契数列是最经典的递归例子之一。定义如下fib(0) 0 fib(1) 1 fib(n) fib(n - 1) fib(n - 2)直接递归写法classSolution{publicintfib(intn){if(n0){return0;}if(n1){return1;}returnfib(n-1)fib(n-2);}}这段代码很符合数学定义但效率很低。为什么因为它会重复计算大量子问题。以fib(5)为例fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ └── fib(1) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)可以看到fib(3)、fib(2)被重复计算了多次。使用记忆化优化如果某个结果已经算过就保存下来下次直接使用。这就是记忆化搜索也是动态规划的重要入口。importjava.util.Arrays;classSolution{publicintfib(intn){int[]memonewint[n1];Arrays.fill(memo,-1);returndfs(n,memo);}privateintdfs(intn,int[]memo){if(n0){return0;}if(n1){return1;}if(memo[n]!-1){returnmemo[n];}memo[n]dfs(n-1,memo)dfs(n-2,memo);returnmemo[n];}}复杂度分析直接递归时间复杂度O(2^n)存在大量重复计算空间复杂度O(n)递归调用栈深度为n记忆化递归时间复杂度O(n)每个状态只计算一次空间复杂度O(n)包括memo数组和递归调用栈递归能直接表达状态关系但如果存在重复子问题就要考虑记忆化或动态规划。递归和循环什么时候用递归什么时候用循环递归和循环都可以解决重复执行的问题但它们适合的场景不完全一样。更适合用循环的情况如果问题是简单的线性重复比如遍历数组求数组最大值计算从1到n的和简单计数通常循环更直接也更节省空间。例如求和intsum0;for(inti1;in;i){sumi;}这类问题虽然可以递归写但实际刷题和工程开发中循环往往更合适。更适合用递归的情况当问题天然具有“分层结构”或“树形结构”时递归会更清晰。常见场景包括树的遍历DFS 搜索回溯枚举分治算法递归定义的数学问题某些动态规划的记忆化搜索写法例如树的结构天然就是递归的一棵树 根节点 左子树 右子树所以树的很多问题都可以写成当前节点怎么处理 左子树递归结果是什么 右子树递归结果是什么对比总结对比项循环递归思维方式重复执行一段逻辑把问题拆成同类小问题空间开销通常较低有调用栈开销适合场景线性遍历、计数树、搜索、分治、回溯风险边界和循环条件错误终止条件错误、栈溢出可读性简单问题更直观结构性问题更清晰线性重复优先考虑循环树形拆分、搜索枚举和分治问题更适合递归。递归模板把代码写稳定递归没有唯一模板但初学阶段可以先记住下面这个结构。返回值类型 函数名(参数列表){if(终止条件){return最小问题的答案;}// 当前层要做的事return递归调用的结果;}如果递归函数不需要返回值常见模板是voiddfs(参数列表){if(终止条件){return;}// 处理当前层dfs(更小规模的问题);// 如果需要处理递归返回后的逻辑}后面学习回溯时还会遇到更完整的模板voidbacktrack(路径,选择列表){if(满足结束条件){收集答案;return;}for(选择:选择列表){做选择;backtrack(路径,新的选择列表);撤销选择;}}这一篇只需要先理解递归函数每一层都在处理一个规模更小的同类问题。递归复杂度不要只看代码短递归代码通常比较短但复杂度不一定低。分析递归复杂度时可以从两个角度看一共有多少次函数调用每次函数调用做了多少工作单分支递归例如intsum(intn){if(n1){return1;}returnnsum(n-1);}调用链sum(n) - sum(n - 1) - sum(n - 2) - ... - sum(1)一共调用n次每次做O(1)工作。所以时间复杂度O(n)空间复杂度O(n)多分支递归例如直接递归计算斐波那契returnfib(n-1)fib(n-2);每一层会分裂出两个递归调用。如果没有记忆化就会产生大量重复计算。所以时间复杂度接近O(2^n)分治递归前面学习归并排序和快速排序时也可以使用递归。以归并排序为例把数组分成两半 分别排序左右两半 再合并递归结构类似sort(left, right) sort(left, mid) sort(mid 1, right) merge(left, mid, right)这种递归虽然有两个分支但每一层总工作量是O(n)层数是O(log n)所以整体复杂度是O(n log n)。递归代码短不代表复杂度低关键要看调用次数、递归深度和是否存在重复子问题。常见坑点递归最容易错在哪里1. 忘记写终止条件错误示例intsum(intn){returnnsum(n-1);}这段代码永远不会停止最终会栈溢出。正确写法intsum(intn){if(n1){return1;}returnnsum(n-1);}2. 递归规模没有变小错误示例intsum(intn){if(n1){return1;}returnnsum(n);}这里递归调用仍然是sum(n)问题规模没有变小。这和没有终止条件一样危险。递归调用应该不断接近终止条件returnnsum(n-1);3. 函数定义不清楚递归最怕写到一半忘记函数本身表示什么。比如写intdfs(intn)你必须明确dfs(n) 到底返回什么是返回前n项和还是返回第n项还是返回从n开始的结果如果函数定义不清楚终止条件和递推关系都会变得混乱。4. 把递归过程想得太细初学者容易试图完整模拟每一层递归。这在简单例子中有帮助但复杂题里会很累。更推荐的思考方式是相信子问题已经被递归函数正确解决 只考虑当前这一层应该做什么例如returnnsum(n-1);你只需要相信sum(n - 1) 能正确返回 1 到 n - 1 的和那么当前层再加上n就可以了。5. 没有意识到递归有栈空间开销递归层数太深时可能会导致栈溢出。例如当n非常大时sum(1000000)即使逻辑正确也可能因为递归层数过深而失败。这时可以改成循环或者在特定语言中使用其他优化方式。在 Java 刷题中深度很大的线性递归通常不如循环稳定。总结递归是很多算法的基础思想。它的核心不是“函数调用自己”这么简单而是把问题拆成结构相同、规模更小的子问题。你可以重点记住下面几句话递归函数必须有明确的函数定义递归必须有终止条件每次递归调用都要让问题规模变小递归会使用调用栈因此有额外空间开销简单线性问题通常循环更稳定树、搜索、回溯、分治等结构性问题很适合递归如果递归存在重复子问题可以考虑记忆化搜索或动态规划递归刚学时会觉得绕是因为你还不习惯“相信子问题已经解决”。当你能清楚写出函数定义、终止条件和递推关系后递归就会从难点变成非常有用的工具。
第16篇-递归入门-为什么很多算法都离不开递归
发布时间：2026/6/15 0:22:17
概述为什么很多算法都离不开递归学完链表之后我们进入一个非常重要的算法思想递归。递归不是某一种具体的数据结构也不是某一道题的固定技巧。它更像是一种解决问题的思维方式把一个大问题拆成一个或多个结构相同的小问题比如求n!可以先求(n - 1)!反转链表可以先反转后面的链表遍历树可以先遍历左子树和右子树回溯搜索可以先处理当前选择再递归处理后续选择动态规划中的状态转移本质上也常常来自递归关系很多初学者觉得递归难主要不是因为代码长而是因为递归执行过程不像循环那样直观。循环是一步一步往前走递归则会不断进入新的函数调用再一层一层返回。这篇文章会从最基础的函数调用开始讲清楚什么是递归递归为什么必须有终止条件递归调用栈是怎么工作的如何写出递归代码递归的常见题型和坑点学完这篇你应该能看懂递归函数的执行过程并能根据“函数定义、终止条件、递推关系”写出基础递归代码。核心概念递归到底是什么递归就是函数在执行过程中调用自己。最简单的形式如下voidfunc(){func();}不过这段代码是错误示范。因为它会无限调用自己永远停不下来最后导致栈溢出。一个正确的递归函数通常长这样voidfunc(intn){if(n0){return;}func(n-1);}这里有两个关键点func(n - 1)把问题规模变小if (n 0)当问题足够小时停止递归递归的本质可以理解成当前问题 当前这一层要做的事 更小规模的同类问题比如求1 2 3 ... nsum(n) n sum(n - 1) sum(1) 1这就是递归关系。递归不是重复写代码而是让函数把问题交给规模更小的自己来解决。递归三要素写递归前先想清楚这三件事写递归时不建议一上来就写代码。更好的方式是先回答三个问题。1. 函数定义是什么也就是这个函数到底要解决什么问题。例如intsum(intn)可以定义为返回 1 到 n 的整数和这个定义非常重要。递归代码能不能写清楚很大程度取决于函数定义是否清楚。2. 终止条件是什么递归必须能停下来。对于sum(n)来说最小问题是sum(1) 1所以终止条件可以写成if(n1){return1;}如果没有终止条件递归会一直调用下去最终出现StackOverflowError。3. 递推关系是什么递推关系就是大问题和小问题之间的关系。对于sum(n)sum(n) n sum(n - 1)对应代码returnnsum(n-1);三个要素合在一起就是完整递归代码intsum(intn){if(n1){return1;}returnnsum(n-1);}递归三要素总结要素要回答的问题示例函数定义这个函数返回什么sum(n)返回1到n的和终止条件什么时候不用继续递归n 1递推关系大问题如何拆成小问题sum(n) n sum(n - 1)先定义函数含义再确定最小问题最后写出大问题和小问题的关系。调用栈递归代码到底是怎么执行的很多人看递归时容易迷糊是因为只看到了代码没有看到函数调用栈。以这段代码为例intsum(intn){if(n1){return1;}returnnsum(n-1);}调用sum(4)执行过程可以分成两个阶段不断向下递归调用到达终止条件后逐层返回调用展开过程sum(4) 4 sum(3) 3 sum(2) 2 sum(1) 1返回过程sum(1) 1 sum(2) 2 1 3 sum(3) 3 3 6 sum(4) 4 6 10如果画成调用栈可以这样理解入栈 sum(4) sum(3) sum(2) sum(1) 出栈 sum(1) 返回 1 sum(2) 返回 3 sum(3) 返回 6 sum(4) 返回 10每一次函数调用系统都会保存当前函数的局部变量、参数和执行位置。这些信息会放到调用栈中。所以递归虽然代码看起来短但它不是没有空间开销。递归层数越深占用的栈空间越多。递归会先不断压栈进入更小问题再从最小问题开始逐层返回答案。例题一计算阶乘题目给定正整数n计算n!。阶乘定义n! n * (n - 1) * (n - 2) * ... * 1例如5! 5 * 4 * 3 * 2 * 1 120解题思路先写函数定义factorial(n) 表示 n 的阶乘终止条件factorial(1) 1递推关系factorial(n) n * factorial(n - 1)Java 代码实现classSolution{publicintfactorial(intn){if(n1){return1;}returnn*factorial(n-1);}}执行过程以factorial(5)为例factorial(5) 5 * factorial(4) 5 * 4 * factorial(3) 5 * 4 * 3 * factorial(2) 5 * 4 * 3 * 2 * factorial(1) 5 * 4 * 3 * 2 * 1 120复杂度分析时间复杂度O(n)从n递归到1空间复杂度O(n)递归调用栈最多有n层例题二数组递归求和题目给定数组nums和下标index递归计算从index到数组末尾的元素和。示例nums [1, 2, 3, 4] sum(nums, 0) 10 sum(nums, 2) 7解题思路函数定义sum(nums, index) 表示 nums[index] 到 nums[nums.length - 1] 的元素和终止条件index nums.length当index已经越过最后一个元素时后面没有元素了返回0。递推关系sum(nums, index) nums[index] sum(nums, index 1)Java 代码实现classSolution{publicintsum(int[]nums,intindex){if(indexnums.length){return0;}returnnums[index]sum(nums,index1);}}为什么终止条件是index nums.length假设数组长度为4合法下标是0, 1, 2, 3当index 4时说明已经没有元素可加了。此时返回0不会影响前面的加法结果。复杂度分析时间复杂度O(n)每个元素处理一次空间复杂度O(n)递归深度最多为数组长度当前结果等于当前元素加上后面所有元素的和。例题三反转字符串题目给定字符数组s请原地反转这个字符数组。示例输入[h, e, l, l, o] 输出[o, l, l, e, h]这道题可以用双指针也可以用递归。递归写法本质上仍然是在模拟左右指针。解题思路定义递归函数reverse(s, left, right) 表示反转 s[left...right] 这一段终止条件left right当左指针和右指针相遇或交错说明反转完成。每一层递归做两件事交换s[left]和s[right]递归反转内部区间s[left 1...right - 1]Java 代码实现classSolution{publicvoidreverseString(char[]s){reverse(s,0,s.length-1);}privatevoidreverse(char[]s,intleft,intright){if(leftright){return;}chartemps[left];s[left]s[right];s[right]temp;reverse(s,left1,right-1);}}执行过程以[a, b, c, d]为例reverse(0, 3)交换 a 和 d - d b c a reverse(1, 2)交换 b 和 c - d c b a reverse(2, 1)left right结束复杂度分析时间复杂度O(n)每个字符最多交换一次空间复杂度O(n)递归调用栈最多约n / 2层如果只考虑最优空间双指针迭代写法可以做到O(1)额外空间。这也说明递归虽然优雅但不一定总是空间最优。例题四斐波那契数列斐波那契数列是最经典的递归例子之一。定义如下fib(0) 0 fib(1) 1 fib(n) fib(n - 1) fib(n - 2)直接递归写法classSolution{publicintfib(intn){if(n0){return0;}if(n1){return1;}returnfib(n-1)fib(n-2);}}这段代码很符合数学定义但效率很低。为什么因为它会重复计算大量子问题。以fib(5)为例fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ └── fib(1) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)可以看到fib(3)、fib(2)被重复计算了多次。使用记忆化优化如果某个结果已经算过就保存下来下次直接使用。这就是记忆化搜索也是动态规划的重要入口。importjava.util.Arrays;classSolution{publicintfib(intn){int[]memonewint[n1];Arrays.fill(memo,-1);returndfs(n,memo);}privateintdfs(intn,int[]memo){if(n0){return0;}if(n1){return1;}if(memo[n]!-1){returnmemo[n];}memo[n]dfs(n-1,memo)dfs(n-2,memo);returnmemo[n];}}复杂度分析直接递归时间复杂度O(2^n)存在大量重复计算空间复杂度O(n)递归调用栈深度为n记忆化递归时间复杂度O(n)每个状态只计算一次空间复杂度O(n)包括memo数组和递归调用栈递归能直接表达状态关系但如果存在重复子问题就要考虑记忆化或动态规划。递归和循环什么时候用递归什么时候用循环递归和循环都可以解决重复执行的问题但它们适合的场景不完全一样。更适合用循环的情况如果问题是简单的线性重复比如遍历数组求数组最大值计算从1到n的和简单计数通常循环更直接也更节省空间。例如求和intsum0;for(inti1;in;i){sumi;}这类问题虽然可以递归写但实际刷题和工程开发中循环往往更合适。更适合用递归的情况当问题天然具有“分层结构”或“树形结构”时递归会更清晰。常见场景包括树的遍历DFS 搜索回溯枚举分治算法递归定义的数学问题某些动态规划的记忆化搜索写法例如树的结构天然就是递归的一棵树 根节点 左子树 右子树所以树的很多问题都可以写成当前节点怎么处理 左子树递归结果是什么 右子树递归结果是什么对比总结对比项循环递归思维方式重复执行一段逻辑把问题拆成同类小问题空间开销通常较低有调用栈开销适合场景线性遍历、计数树、搜索、分治、回溯风险边界和循环条件错误终止条件错误、栈溢出可读性简单问题更直观结构性问题更清晰线性重复优先考虑循环树形拆分、搜索枚举和分治问题更适合递归。递归模板把代码写稳定递归没有唯一模板但初学阶段可以先记住下面这个结构。返回值类型 函数名(参数列表){if(终止条件){return最小问题的答案;}// 当前层要做的事return递归调用的结果;}如果递归函数不需要返回值常见模板是voiddfs(参数列表){if(终止条件){return;}// 处理当前层dfs(更小规模的问题);// 如果需要处理递归返回后的逻辑}后面学习回溯时还会遇到更完整的模板voidbacktrack(路径,选择列表){if(满足结束条件){收集答案;return;}for(选择:选择列表){做选择;backtrack(路径,新的选择列表);撤销选择;}}这一篇只需要先理解递归函数每一层都在处理一个规模更小的同类问题。递归复杂度不要只看代码短递归代码通常比较短但复杂度不一定低。分析递归复杂度时可以从两个角度看一共有多少次函数调用每次函数调用做了多少工作单分支递归例如intsum(intn){if(n1){return1;}returnnsum(n-1);}调用链sum(n) - sum(n - 1) - sum(n - 2) - ... - sum(1)一共调用n次每次做O(1)工作。所以时间复杂度O(n)空间复杂度O(n)多分支递归例如直接递归计算斐波那契returnfib(n-1)fib(n-2);每一层会分裂出两个递归调用。如果没有记忆化就会产生大量重复计算。所以时间复杂度接近O(2^n)分治递归前面学习归并排序和快速排序时也可以使用递归。以归并排序为例把数组分成两半 分别排序左右两半 再合并递归结构类似sort(left, right) sort(left, mid) sort(mid 1, right) merge(left, mid, right)这种递归虽然有两个分支但每一层总工作量是O(n)层数是O(log n)所以整体复杂度是O(n log n)。递归代码短不代表复杂度低关键要看调用次数、递归深度和是否存在重复子问题。常见坑点递归最容易错在哪里1. 忘记写终止条件错误示例intsum(intn){returnnsum(n-1);}这段代码永远不会停止最终会栈溢出。正确写法intsum(intn){if(n1){return1;}returnnsum(n-1);}2. 递归规模没有变小错误示例intsum(intn){if(n1){return1;}returnnsum(n);}这里递归调用仍然是sum(n)问题规模没有变小。这和没有终止条件一样危险。递归调用应该不断接近终止条件returnnsum(n-1);3. 函数定义不清楚递归最怕写到一半忘记函数本身表示什么。比如写intdfs(intn)你必须明确dfs(n) 到底返回什么是返回前n项和还是返回第n项还是返回从n开始的结果如果函数定义不清楚终止条件和递推关系都会变得混乱。4. 把递归过程想得太细初学者容易试图完整模拟每一层递归。这在简单例子中有帮助但复杂题里会很累。更推荐的思考方式是相信子问题已经被递归函数正确解决 只考虑当前这一层应该做什么例如returnnsum(n-1);你只需要相信sum(n - 1) 能正确返回 1 到 n - 1 的和那么当前层再加上n就可以了。5. 没有意识到递归有栈空间开销递归层数太深时可能会导致栈溢出。例如当n非常大时sum(1000000)即使逻辑正确也可能因为递归层数过深而失败。这时可以改成循环或者在特定语言中使用其他优化方式。在 Java 刷题中深度很大的线性递归通常不如循环稳定。总结递归是很多算法的基础思想。它的核心不是“函数调用自己”这么简单而是把问题拆成结构相同、规模更小的子问题。你可以重点记住下面几句话递归函数必须有明确的函数定义递归必须有终止条件每次递归调用都要让问题规模变小递归会使用调用栈因此有额外空间开销简单线性问题通常循环更稳定树、搜索、回溯、分治等结构性问题很适合递归如果递归存在重复子问题可以考虑记忆化搜索或动态规划递归刚学时会觉得绕是因为你还不习惯“相信子问题已经解决”。当你能清楚写出函数定义、终止条件和递推关系后递归就会从难点变成非常有用的工具。
