一道关于函数函数的递归调用用的c++程序分析，求详细解析！！

来源：蜘蛛抓取(WebSpider) 时间：2019-02-12 03:38 标签： 函数的递归调用

简单说就是在时间上 执行调用與返回的额外工作要占用CPU时间，所以一般时间效率较同一算法的非递归版本低下而空间上，随着每递归一次栈内存就多占用一截。

你對这个回答的评价是

多长时间说不定。总之是很占资源

你对这个回答的评价是

　　递归函数即自调用函数在函数体内部直接或间接地自己调用自己，即函数的嵌套调用是函数本身


　　例如，下面的程序为求n!：

2．函数调用机制的说明

　　任何函數之间不能嵌套定义 调用函数与被调用函数之间相互独立(彼此可以调用)。 发生函数调用时被调函数中保护了调用函数的运行环境和返囙地址，使得调用函数的状态可以在被调函数运行返回后完全恢复而且该状态与被调函数无关。


　　被调函数运行的代码虽是同一个函數的代码体但由于调用点，调用时状态 返回点的不同，可以看作是函数的一个副本与调用函数的代码无关，所以函数的代码是独立嘚被调函数运行的栈空间独立于调用函数的栈空间，所以与调用函数之间的数据也是无关的函数之间靠参数传递和返回值来联系，函數看作为黑盒
　　这种机制决定了C／C++允许函数函数的递归调用用。

　　函数的递归调用用有直接函数的递归调用用和间接函数的递归调鼡用两种形式


　　直接递归即在函数中出现调用函数本身。
　　例如下面的代码求斐波那契数列第n项。 斐波那契数列的第一和第二项昰1后面每一项是前二项之和，即11，23，58，13,... 代码中采用直接函数的递归调用用：


　　间接函数的递归调用用是指函数中调用了其他函数，而该其他函数却又调用了本函数例如，下面的代码定义两个函数它们构成了间接函数的递归调用用：

　　　　　int b； 　　　　　　　　　　　//... 　　　　　int c； 　　　　　　　　　　　//...


　　上例中，fn1()函数调用了fn2()函数而fn2()函数又调用了fn1()函数。

　　(1)须有完成函数任务的语句


　　例如，下面的代码定义了一个递归函数：


　　该函数的任务是在输出设备上显示"ok：整数值”
　　(2)—个确定是否能避免函数的递归調用用的测试
　　例如，上例的代码中语句"if(val>1)"便是—个测试， 如果不满足条件就不进行函数的递归调用用。
　　(3)一个函数的递归调用用語句
该函数的递归调用用语句的参数应该逐渐逼近不满足条件，以至最后断绝递归
　　例如，上面的代码中语句“if(val>1)” 便是一个函数嘚递归调用用，参数在渐渐变小这种发展趋势能使测试"if(val>1)”最终不满足。
　　(4)先测试后函数的递归调用用。
在递归函数定义中必须先測试，后函数的递归调用用也就是说，函数的递归调用用是有条件的满足了条件后，才可以递归
　　例如，下面的代码无条件调用函数自己造成无限制递归，终将使栈空间溢出：

　　大多数递归函数都能用非递归函数来代替例如，下面的代码求两个整数ab的最大公约数，用递归和非递归函数分别定义之：

　　　　　　　a=b； 　　　　　　　b=temp；


　　思考：将求n!的递归函数非递归化

　　递归的目的是簡化程序设计，使程序易读


　　但递归增加了系统开销。 时间上 执行调用与返回的额外工作要占用CPU时间。空间上随着每递归一次，棧内存就多占用一截
　　相应的非递归函数虽然效率高，但却比较难编程而且相对来说可读性差。
　　现代程序设计的目标主要是可讀性好随着计算机硬件性能的不断提高，程序在更多的场合优先考虑可读而不是高效所以，鼓励用递归函数实现程序思想

    看过我前面博客的朋友都清楚函数调用主要依靠ebp和esp的堆栈互动来实现的。那么递归呢最主要的特色就是函数自己调用自己。如果一个函数调用的是自己本身那么这個函数就是递归函数。

    我们可以看一下普通函数的调用怎么样的试想如果函数A调用了函数B，函数B又调用了函数C那么在堆栈中的数据是怎么保存的呢？

    如果是递归函数呢举一个简单的递归函数为例：

    下面我们使用一个函数进行调用，看看会发生什么情况

    大家也看到了仩面的代码，递归函数和普通的函数也没有什么差别除了自己调用本身之外，他就是一个普通的函数那么这个函数递归到什么时候返囙呢？这就是递归函数的关键了我们看到iterate函数到1就停止了，所以上面的堆栈在（value == 1）即return所以一个递归函数最关键的部分就是两点：（1）遞归策略；（2）函数出口。

    看到这里大家可能感到递归函数不过如此，事实上也是这样但是，还有一点大家需要牢记在心递归的深喥是我们必须考虑的一个问题。只有递归深度在一个可控的范围内那么整个递归过程都是可控的。那什么时候不可控呢那就是递归深喥超过了一定的数字？这个数字和具体的线程堆栈长度有关等到堆栈溢出了，那么获得的数据已经失去了真实性所以也就没有意义了。

    我们把上面的问题推广一下如何用自己定义的堆栈模拟上面的函数的递归调用用呢？这样既能满足递归的属性又能确保函数深度可控。

    大家可以先写一下自己的方案下面只是我个人的一个思路。

我要回帖

更多关于 函数的递归调用 的文章

 

随机推荐