数据结构-递归算法

一、递归的核心概念递归Recursion是程序设计中的一种重要思想指的是函数直接或间接调用自身的编程技巧。其核心逻辑是“大事化小”——将一个复杂的大问题拆解成与原问题结构相同但规模更小的子问题直到子问题小到可以直接解决即递归终止条件再通过子问题的解反向推导得到原问题的解。形象地说递归就像“俄罗斯套娃”每个套娃的结构都相同打开外层套娃会看到更小的套娃直到打开最里面的小娃娃终止条件整个拆解过程就结束了。能用递归解决问题要满足三个条件:子问题与原问题结构一致拆解后的子问题必须和原问题的解决逻辑、数据结构完全相同仅问题规模更小。这样才能保证递归函数可复用自身逻辑处理子问题形成“大事化小”的拆解链条。递归的调用次数有限每次递归调用时必须使问题规模向终止条件的方向递减。如果问题规模不缩小甚至扩大即使存在终止条件也可能因无法触及临界值而陷入无限递归。存在明确的递归终止条件必须有一个清晰的“出口”当问题规模缩小到某个临界值时不再调用自身直接返回确定的结果。若缺少终止条件会导致函数无限递归最终引发栈溢出错误。二、递归的工作原理深入理解后面有图片演示帮组理解C语言中函数调用会在内存的“栈区”开辟一块独立的栈帧用于存储函数的参数、局部变量等信息栈区由系统自动管理速度快但空间小存储局部变量。递归调用的本质是多次重复这个“开辟栈帧”的过程具体分为两个阶段1. 递推阶段拆解问题函数每次调用自身时都会将当前的参数、局部变量等信息压入栈中然后处理规模更小的子问题。这个过程会一直持续直到达到递归终止条件。2. 回溯阶段合并结果当子问题得到解决后函数会从栈中弹出之前压入的信息恢复到上一层函数的执行环境然后结合子问题的解计算当前层的结果。这个过程逐层回溯最终得到原问题的解。三、C语言递归示例详解下面通过4个典型示例从简单到复杂帮助大家深入理解递归的使用场景和实现逻辑。示例1计算n的阶乘最基础递归1. 问题分析f(n)1; n1f(n)n*f(n-1) n1第一个式子给出了递归的终止条件递归出口第二个式子给出了f(n)与f(n-1)之间的关系递归体。2. 代码实现#include stdio.h // 递归计算n的阶乘 int factorial(int n) { // 递归终止条件n0或n1时阶乘为1 if (n 0 || n 1) { return 1; } // 递推n! n * (n-1)!调用自身处理子问题(n-1)! return n * factorial(n - 1); } int main() { int n 5; printf(%d! %d\n, n, factorial(n)); return 0; } // 输出结果5! 1203. 了解这段阶乘递归代码在栈内存中的实现过程深入理解递归的实现机制一、栈内存的核心工作机制程序运行时的 栈Call Stack也叫执行栈是一块先进后出LIFO的内存区域专门用于管理函数调用过程。当发生函数调用时系统会在栈顶为被调用函数创建一块独立的内存空间称为「栈帧 / 活动记录」当函数执行完毕返回值或执行结束对应的栈帧会从栈顶弹出内存被释放执行流程回到调用函数的断点处继续执行。以n5为例递归调用会从factorial(5)开始逐层分解为子问题每一层调用都会创建新栈帧栈的增长方向是从高地址向低地址延伸栈顶指针向下移动具体入栈顺序如下第一步主函数main()调用factorial(5)main()函数先拥有一个栈帧保存main()的局部变量n5、返回地址程序入口的下一条指令等信息。当执行printf中的factorial(5)时系统在栈顶创建factorial(5)的栈帧然后跳转到factorial函数的执行逻辑。第二步factorial(5)调用factorial(4)factorial(5)的栈帧中保存参数n5、返回地址回到5 * factorial(4)的计算逻辑、函数执行上下文。由于n5不满足终止条件执行return 5 * factorial(4)触发对factorial(4)的调用系统在栈顶factorial(5)栈帧下方创建factorial(4)的栈帧。第三步factorial(4)调用factorial(3)factorial(4)栈帧保存参数n4、返回地址回到4 * factorial(3)的计算逻辑。不满足终止条件调用factorial(3)创建factorial(3)栈帧位于factorial(4)栈帧下方。第四步factorial(3)调用factorial(2)栈帧保存n3和返回地址回到3 * factorial(2)调用factorial(2)创建对应栈帧。第五步factorial(2)调用factorial(1)栈帧保存n2和返回地址回到2 * factorial(1)调用factorial(1)创建对应栈帧。终止factorial(1)满足递归终止条件factorial(1)栈帧保存n1此时触发if (n0 || n1)直接返回 1无需继续调用子函数。此时栈中从栈底到栈顶的栈帧顺序为main()→factorial(5)→factorial(4)→factorial(3)→factorial(2)→factorial(1)栈顶为factorial(1)。单个栈帧的核心组成结构了解每个factorial(n)函数的栈帧包括main()都包含以下关键部分不同编译器略有差异但核心一致返回地址Return Address保存当前函数执行完毕后需要回到的调用函数的指令地址例如factorial(1)的返回地址是factorial(2)中2 * factorial(1)的计算指令地址。函数参数Parameters保存传入函数的参数值例如factorial(5)的栈帧中保存参数n5factorial(1)的栈帧中保存n1。局部变量Local Variables保存函数内部定义的局部变量本例中factorial函数无额外局部变量main()函数的栈帧中保存局部变量n5。栈基址指针EBP栈帧指针用于固定当前栈帧的起始位置方便访问栈帧内的参数、局部变量相当于栈帧的 “锚点”。栈顶指针ESP指向当前栈顶的位置随着栈帧的创建和销毁动态移动创建栈帧时 ESP 减小释放栈帧时 ESP 增大。临时数据 / 执行上下文保存函数执行过程中产生的临时计算结果、寄存器状态等。二.递归返回与栈帧销毁过程逐层出栈计算结果了解递归的返回过程遵循「先进后出」原则从栈顶的factorial(1)开始逐层销毁栈帧并计算阶乘结果具体流程如下factorial(1)返回栈帧销毁factorial(1)执行return 1将返回值 1 存入指定寄存器如 EAX。factorial(1)的栈帧从栈顶弹出ESP 上移释放内存执行流程通过返回地址回到factorial(2)的断点处2 * factorial(1)。factorial(2)计算并返回栈帧销毁factorial(2)从寄存器中获取factorial(1)的返回值 1执行计算2 * 1 2。执行return 2将结果 2 存入寄存器随后factorial(2)栈帧销毁流程回到factorial(3)的断点处3 * factorial(2)。factorial(3)计算并返回栈帧销毁获取factorial(2)的返回值 2计算3 * 2 6返回 6 并销毁栈帧流程回到factorial(4)。factorial(4)计算并返回栈帧销毁获取返回值 6计算4 * 6 24返回 24 并销毁栈帧流程回到factorial(5)。factorial(5)计算并返回栈帧销毁获取返回值 24计算5 * 24 120返回 120 并销毁栈帧流程回到main()函数。main()函数接收结果并输出main()从寄存器中获取factorial(5)的返回值 120执行printf(%d! %d\n, 5, 120)输出结果5! 120。main()函数执行完毕后其栈帧也被销毁程序正常退出。至此所有递归栈帧均已销毁栈内存恢复到程序启动前的状态。总结递归调用的核心是调用栈的逐层入栈创建栈帧和逐层出栈销毁栈帧遵循先进后出原则每个递归函数调用都会创建独立栈帧保存参数、返回地址等关键信息这是递归能记住“上一层调用状态” 的原因阶乘递归的栈帧变化从factorial(5)到factorial(1)入栈再从factorial(1)到factorial(5)出栈并计算结果最终得到 120。四.递归算法的设计步骤1.明确递归的结束条件和递归终止时的处理方法。2.确定求解问题的递归模型。技巧你在设计递归算法时切勿层层展开子问题使得问题复杂化,不如只考虑递归中第一层于第二层之间的关系不确定加上第三层与第二层的关系是否与之一样加上 1.即可求出递归模型。如知道 55*4 44*3加上11 求出f(n)1; n1f(n)n*f(n-1) n1的递归模型求解阶乘就能解决问题了。五.示例2计算斐波那契数列经典递归问题1. 问题分析斐波那契数列定义第1项和第2项均为1从第3项开始每一项等于前两项之和即F(n) F(n-1) F(n-2)n≥3。 终止条件F(1)1F(2)1。F(1)1 n1F(2)1 n1F(n) F(n-1) F(n-2) n32.代码#define _CRT_SECURE_NO_WARNINGS #include stdio.h int fib(int n) { if (n 1 || n 2) { return 1; } else return fib(n - 1) fib(n - 2); } int main() { int a 0; scanf(%d, a); int b fib(a); printf(%d, b); }