递归算法：从入门到精通的实战指南

一、递归核心定义函数自身调用自身把大问题不断拆分成同类型小问题满足两个必备条件即可使用递归问题能拆分为规模更小的同类子问题存在明确终止边界避免无限调用执行流程递推分解 → 触底终止 → 逐层回溯返回结果二、递归三要素解题必按此分析终止条件最小不可拆分问题直接返回结果递归拆解原问题拆分出子问题缩小问题规模结果合并子问题答案整合得到最终解三、入门经典例题例题 1求 n 的阶乘公式(n! n*(n-1)!)0! 1int factorial(int n) { // 终止条件 if(n 0 || n 1) return 1; // 拆解合并 return n * factorial(n - 1); }例题 2斐波那契数列(f(n)f(n-1)f(n-2))(f(1)1,f(2)1)int fib(int n) { if(n 1 || n 2) return 1; return fib(n-1) fib(n-2); }例题 3链表递归求和struct ListNode { int val; ListNode* next; ListNode(int x):val(x),next(nullptr){} }; int sumList(ListNode* head) { // 终止条件 if(!head) return 0; // 当前值 后续链表和 return head-val sumList(head-next); }四、递归解题通用步骤确定函数功能明确输入参数、返回值含义寻找边界写出最小规模终止条件拆分问题把当前问题转化为子问题整合结果根据题意组合子问题答案测试边界值排查死递归、返回错误问题五、递归优缺点优点代码简洁凝练逻辑贴合问题本身树、图、路径搜索、排列组合问题写法直观无需手动维护循环变量减少边界错误缺点存在递归调用栈深度过大易栈溢出重复计算多部分场景效率偏低层数太深时调试排查难度大六、递归常见优化方式记忆化递归数组存储已算结果避免重复计算迭代改写循环替换递归规避栈溢出剪枝提前剔除无效分支减少递归次数记忆化斐波那契示例cpp运行int memo[50]; int fibMemo(int n) { if(n1||n2) return 1; if(memo[n] ! 0) return memo[n]; memo[n] fibMemo(n-1)fibMemo(n-2); return memo[n]; }七、递归高频适用题型数学计算阶乘、斐波那契、幂运算二叉树遍历、树深度、路径统计DFS 深度搜索、岛屿遍历排列、组合、子集回溯类题目链表反转、链表拆分八、新手高频易错点遗漏终止条件程序无限递归崩溃问题拆分逻辑错误子问题和原问题不同类参数传递不变问题规模没有缩小递归返回值处理不当无法合并正确结果忽略栈溢出风险处理超大层数数据九、今日总结递归本质大事化小函数自调用求解子问题解题核心三要素终止条件、问题拆分、结果合并简单场景代码极简复杂搜索场景优势明显熟记基础例题为后续回溯算法打好基础