《数据结构与算法之美》07——递归
2021-05-11 11:27
标签：strong 调度 比较 spl mil 问题 表达 color 堆栈 一、如何理解“递归” 递归是一种应用非常广泛的算法（或者编程技巧）。 二、递归的三个条件 1、一个问题的解可以分解为几个子问题的解 2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 3、存在递归终止条件 三、如何编写递归代码 写递归代码最关键的是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再失调终止条件，最后将递推公式和终止条件，最后将递推公式和终止条件翻译成代码。 四、递归代码的注意事项 1、递归代码要警惕堆栈溢出 函数调用的机制是通过堆栈来实现的，递归代码层次过深会容易溢出堆栈空间。 2、递归代码要警惕重复计算 递推公式分解时，会存在大量重复计算。 五、递归代码改写为非递归代码 递归代码有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。 在开发过程中，要根据实际情况来选择是否需要用递归的方式来实现。 是否所有的递归代码都可以改为迭代循环的非递归写法？ 笼统地讲，是的。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知而已。 六、课后思考 我们平时调试代码喜欢使用IDE的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？ 递归使用不多，没有遇到过类似的问题，但感觉可以使用单元测试来调度，不管是通过进行查看结果，也能Mock数据来验证递归公式是否正确。 《数据结构与算法之美》07——递归 标签：strong 调度 比较 spl mil 问题 表达 color 堆栈 原文地址：https://www.cnblogs.com/liang24/p/13153863.html
下一篇：基本语言（二）