递归和阶乘的效率比较
转自:https://www.pureweber.com/article/recursive-power-4/
递归的力量(四):递归效率
前几天我们在讨论递归的过程中发现,递归在解决某些问题的时候使得我们思考的方式得以简化,代码也更加精炼,容易阅读。那么既然递归有这么多的优点,我们是不是什么问题都要用递归来解决呢?难道递归就没有缺点吗?今天我们就来讨论一下递归的不足之处。
我们知道,递归调用实际上是函数自己在调用自己,而函数的调用开销是很大的,系统要为每次函数调用分配存储空间,并将调用点压栈予以记录。而在函数调用结束后,还要释放空间,弹栈恢复断点。所以说,函数调用不仅浪费空间,还浪费时间。
这样,我们发现,同一个问题,如果递归解决方案的复杂度不明显优于其它解决方案的话,那么使用递归是不划算的。因为它的很多时间浪费在对函数调用的处理上。在C++中引入了内联函的概念,其实就是为了避免简单函数内部语句的执行时间小于函数调用的时间而造成效率降低的情况出现。在这里也是一个道理,如果过多的时间用于了函数调用的处理,那么效率显然高不起来。