递归

递归是算法是简洁、优美、强大的,递归简单地说就是把自身越来越小的形式表示和解决。

递归计算机中是如何实现的呢?

我们需要对函数调用做些了解。一个可执行文件被加载到虚拟存储器中, 其中的数据由以下几个区域组成,程序和代码(代码段),堆,共享库和静态数据区,栈。当进程调用一个函数时,就需要在栈中保存和这个调用相关的信息。栈上的这部分空间我们称为栈帧。栈帧中包括输入参数、返回值的空间、计算使用到的临时空间(比如c语言函数内部使用到的变量,在函数返回后,因为栈帧被弹出而自动清除),调用函数保存的状态信息及输出参数等。一个方法的输出参数会成为下一个调用函数的输入参数。栈帧在调用函数时压入栈中,当函数返回时才从栈中弹出。

有上面的描述我们可以推出递归函数是如何执行的,递归递归,递推加回归,在递推过程时函数通过不断调用自己来执行,然后当其中的调用满足结束条件时,递推阶段结束,开始回归操作,在回归操作中,其以递推逆序的方式执行,直到最初的函数返回。

可以看到每次调用自身的时候都需要一个栈帧来保存现场,这会占用大量的空间来存储他们,同时也因为大量信息的保存和恢复,生成和销毁他们也要花费大量时间。

有没有办法可以消除这个缺点呢?有的,如果一个函数所有递归调用都出现在函数末尾,那么我们称其为尾递归。

尾递归可以替换成等价的迭代实现,不会改变程序结果,但可以节省函数调用的开销。现代的编译器通常能够检测到尾递归,当检测到时,其会覆盖当前栈帧,而不重新创建一个,这样空间和时间上都节省不少。

我们再考虑一种情况,如果递归函数的终止条件永远得不到满足,最后程序栈会增加到超过系统可以接受的最大限度,产生栈溢出而终止执行。

另外在很多系统实现时都会把递归的算法改成迭代的算法,也是出于对函数执行效率的考虑,比如数据库最重要的算法二分查找算法,快速排序算法,都是采用的迭代算法。

但是递归还是非常有用处的,递归的算法比较容易理解算法本身,所以在许多数据结构和算法的书中都会有以递归算法来讲解算法实现。

Leave a Reply

Your email address will not be published. Required fields are marked *