递归小论（3）

本文主要是介绍递归小论（3），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

请扫码加公众号

太多太多的高效算法的受递归类型的，快排，堆排序，二叉树的各类算法，顺序统计，BFS,DFS……

，

递归的东西实在太多，似乎计算机科学家们特别钟爱递归

 

为什么那么多的高效算法的都是递归的，是因为递归能提高程序的运行速度吗？

 

事实上，递归并不能提高程序运行的速度，反而会降低程序运行的速度。

 

函数栈

递归在不断的调用自身的过程中相当于不断在内部调用新的函数，操作系统为了这个就必须的不断为其分配空间。

这种申请是动态的，如果递归层次不算太深，时间仅仅浪费在为每个函数的栈帧空间分配地方。也就是在进程内已分配到的页也许已经够用。

问题出在往往递归程度很深，系统甚至需要为了这个进程去分配新的页来存储这些额外的空间开销。

另一方面，我们甚至至可能需要考虑到内存和磁盘之间的数据交换，这样一来程序的速度会更慢。（我们在编程时候使用的内存地址都是逻辑地址，并不是实际的物理地址，一个程序往往得到的内存不会特别大，更不可能达到4G，8G那么大）。

 

因为递归会减慢程序的速度，国内有的教材甚至把很多递归的算法写了循环的形式。“一切为了效率”。

 

然而，递归还是被广泛使用着，我相信将来递归还会被广泛使用。

 

原因在于递归可以说并不是一项技术，而是一种思考模式，这种pattern是机器思考的模式，（今天看了模仿游戏有点迷 讲图灵的 特别喜欢那句机器的思考方式只是与人类不同 blablabla）。

 

递归简单讲就是，机器手上有这最基本的情况，现在给定任何一种情况，都可以慢慢转化成最基本的情况，然后在步步为营，回到最初解决给定的情况。

 

这种思维模式人类很难做到，求4！还算简单，倘若给一个序列说让手动使用归并排序来排序它，我相信我们的速度往往比不上直接看得排序（直接看直接排，根据心情排）

 

把一个递归程序翻译成循环相当于手动排序，只是说“手动”得更高级而已（若是不使用递归，那么就必须得知道怎样从递归底层走到所求问题，也就是对机器怎么归并排序要了如指掌）。

 

 

与我们相反，计算机很擅长干这种事情，只要在硬件上没有问题，它便能确定无疑的一步一步往回走，而且反应速度和人类相比根本不是一个量级

 

被广泛使用的另一个原因是理论分析方便。

具体点就是分析渐进复杂度问题会快很多，大部分的递归问题都遵从分而治之思想，所以最后的递归式子往往会变成

T（n）=aT(n/k)+O(*)

这种形式，这种形式已经有了比较系统的主方法能够解决。

简单说，递归的理论分析如果在有了算法以后往往只是几分钟的事情。

 

支持递归的另一个原因是使用了递归以后，程序的可能性会好很多，如果真的要写成循环其实是需要很大篇幅的。

然则，换成递归以后往往只有几行，一般递归底层定对了就不太会出错，这样代码给别的程序员阅读的时候，程序员只需要理解递归的思路即可，无需煞费心血得理解循环要表达的是什么，如果存在更换程序员的情况，也不太可能出现说看不懂前一个程序员代码的尴尬情况。

这篇关于递归小论（3）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---