大家好，近很多小伙伴想了解递归下降，下面是小编整理的与递归下降相关的内容分享给大家，一起来看看吧。

本文目录一览：

• 1、递归的原理解释
• 2、递归下降法属于
• 3、为什么说递归效率低？

递归的原理解释

递归的原理解释：

递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。

递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。定某个调用函数调用了一个被调用函数，再定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。

程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

递归下降法属于

递归下降法属于自顶向下分析法。在高级语言编译程序常用的语法分析方法中，递归下降法属于自顶向下分析法。

为什么说递归效率低？

对于递归，有人提到了两点：

（1）对栈的容量的压力。

（2）个别问题的递归解法，其算法的低效性。

这两个因素我简短点评下，

（1）对栈的容量压力：

通常递归的深度很大造成的。对于这一点当然应该有程序员编码时，来衡量和把握。win32 中一个新建的线程，默认的栈通常在 1 MB 大小。那么如果你的递归函数，深度很大，显然程序员应该对这种情况有预估，和对风险的避免。

这就和你选择，把内存分配在栈上还是堆上，会考虑到分配的内存大小的因素一样。

当然，如果在函数内分配很大的栈上空间，在函数体内定义一个很大的数组，这样不需要很深的深度，也会让栈溢出。这当然也是程序员自己应该控制的。

（2）个别问题的递归解法，算法的低效。

这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如说求斐波那契的某一项，子问题会大量重复出现，会产生很多重复计算，这个是很多算法书上，是用来引导出动态规划或者查表法的。

这主要是算法本身的效率问题，而不是递归的问题。这一点是必须应该明确的。

（3）我们可以看到，在和树有关的算法中，经常会有递归函数。

例如，遍历文件夹，删除注册表的某一个 key （及其所有子key）。

尤其对一般树的前序，后序遍历，二叉树的中序遍历。

这主要原因是因为树的定义，就是“递归性”的：

树就是，某一个节点有多个子节点，每个子节点是一个树。

我们再此可以看到，递归的显著优点，是对解的描述的直观性，代码的简洁性。

以上就是递归下降的介绍，希望能对大家有所帮助。

获赞：346

收藏：92

回答时间：2024-05-14 00:40:20