目录引言一.函数的递归1.定义2.持续递归3.抽象解释4.递归的核心要素5.递归的使用抽象解释6.递归的特点二.递归与循环引言函数的递归不只是函数的套娃调用更是把问题层层拆解逐层还原的思维方式是连接数学算法与程序设计的桥梁。其意义在于以自相似方式拆解问题它贴近数学归纳与分治回溯树遍历等算法使代码简洁结构清晰同时提醒我们注意边界调用栈与性能是重要的思维方式。一.函数的递归1.定义递归是编程的一种技术——一个函数在其定义内部调用自身递归一定是依赖于函数的2.持续递归一直调用会死递归栈溢出使程序崩掉3.抽象解释递归相当于“镜子中的镜子”或“俄罗斯套娃”把一个大型的复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了4.递归的核心要素1递归调用递推阶段函数自己调用自己每次调用时问题都应该比上一次更小逐步逼近一个最简单的“基础情况”2终止条件基础情况一个不再进行递归调用能直接返回结果的特定条件如果没有终止条件递归会无限进行下去最终导致栈溢出错误5.递归的使用抽象解释写递归可先写完成步骤拆分然后将其按步骤包装先执行结束前的最后一步[若前无语句]不需要再拆分的那步及其对应的语句或将函数功能当成已经实现的将其单独写明判断后再实现要求的最后一步即可/含该函数的式子需格外注意递归要有条件且每次递归都要更逼近条件6.递归的特点用少量的代码完成大量的运算会占用较多内存1数值过大时反应时间长在一些问题中如计算斐波那列数列在数值过大时会因为反复计算子问题导致时间复杂度指数级增加最终占用过多时间使程序性能堪忧2栈溢出I.C语言中每次调用函数都需要为本次函数在内存的栈区上申请一块内存空间来保存函数调用期间各种局部变量的值——这块空间叫做运行时堆栈或函数栈帧函数如果不返回函数表对应栈帧空间就会被一直占用II.因此如果函数调用中存在递归调用时每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归时才会逐层释放栈帧空间若采用函数递归的方式完成代码递归层次过大或过深就会浪费大量栈帧空间也坑能引起栈溢出的问题III.关于上述问题可用循环来解决IV.另一种优化递归程序中栈溢出的方式——尾递归不一定可靠二.递归与循环有时用递归只是因为他比非递归更清晰但有时循环实现效率更高递归一个问题非常复杂难以用循环方式实现此时递归实现的简洁性可以补偿它所带来的运行时开销一般情况下递归深度100层并且不会带来大量冗余计算时可以大胆使用递归写法循环当这个问题使用递归解决存在明显缺陷时需要考虑循环方式递归长会使用到树/图遍历分治算法回溯算法在数据结构中会大量使用