数据结构:第十章 - 递归 & 分治 602次阅读 数据结构 2022-08-02 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、递归 ## (一)概念 * 程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 > 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。 > * 递归的能力在于用有限的语句来定义对象的无限集合。 ## (二)需满足的要求: * 边界条件与递归方程是递归函数的两个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。 > 递归中需要的成分是递归边界和递归规则,没有递归边界递归无法停止、无法进行。 > * 通过将各层的关系从小到大逐渐带入,可以求解出一个函数的非递归表达式。 * n 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 ## (三)优缺点: * 优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,为设计算法、调试程序带来很大方便。 * 缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多,容易导致栈的溢出。 > 由于栈的后进先出特点,所以栈特别方便用来保存 /恢复调用现场,因此递归算法常用栈来实现。 ## (四)对递归中栈的补充: 栈维护了每个函数调用的信息直到函数返回后才释放,这需要占用相当大的空间,尤其是在程序中使用了许多的递归调用的情况下。所以递归容易导致栈的溢出。 幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。 尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、分治 ## (一)定义 * 将规模为 n 的问题分为 k 个规模较小的子问题。子问题和原问题相同且相互独立。递归地解决子问题并将子问题的解合并为原问题的解。 * 分治算法在于“分”与“治”。 ## (二)需满足的要求 * 问题的规模缩小到一定的程度就可以解决。 * 该问题可以分成若干个规模较小的子问题。 * 该问题分解出的子问题的解可以合并成为问题的解。 * 问题没有重叠的子问题。 ## (三)步骤 1. 解决小规模的问题。 2. 分解问题。 3. 递归的解各子问题。 4. 将各子问题的解合并为原问题的解。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 1 最后一次更新于2022-10-23 数据结构
0 条评论