递归过程

出自 MBA智库百科(https://wiki.mbalib.com/)

　　递归过程指栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。递归是程序设计中一个强有力的工具。

　　一个直接调用自己或通过一系列的过程调用语句间接调用自己的过程，称作递归过程。

　　当一个过程的运行期间调用另一个过程时，在执行被调用过程之前，系统需先完成如下三件事：

　　1、将所有的实在参数，返回地址等信息传递给被调用的过程保存。

　　2、为被调用过程的局部变量分配存储空间。

　　3、将控制转移到被调用入口。

　　从被调过程返回调用过程

　　1、保存被调用过程的计算结果。

　　2、释放被调用过程的数据区。

　　3、依照被调过程保存的返回地址将控制转移到调用过程。

　　服从后调用先返回的原则。

　　基本原理是重复的把原问题转换为相似的新问题，直到把问题解决为止。

　　关键点：

　　1、用较简单的问题来表示较复杂的问题。

　　2、不能产生自己调用自己的无穷序列。即必须要有一个是递归出去的出口。。

　　递归的调用时通过栈来实现的。

　　“递归”过程是指调用自身的过程。通常，这不是编写VisualBasic代码的最有效方法。

　　其一，有很多数学函数是递归定义的，如大家熟悉的阶乘函数Fact（n）=1若n=1Fact（n）=n·Fact（n-1）若n>12阶Fibonacci数列Fib（n）=0若n=0Fib（n）=1若n=1Fib（n）=Fib（n-1）+Fib（n-2）其它情形和ackerman函数Ack（m，n）=n+1m=0Ack（m，n）=Ack（m-1，1）n=0Ack（m，n）=Ack（m-1，Ack（m,n-1））其它情形等；

　　其二，有的数据结构，如二叉树，广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述；

　　其三，还有一类问题，虽则问题本身没有明显的递归结构，用递归求解比迭代求解更简单，如八皇后问题，Hanio塔问题等。

　　限制条件。您在设计一个递归过程时，必须至少测试一个可以终止此递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理。如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之中。

　　内存使用。应用程序的局部变量所使用的空间有限。过程在每次调用它自身时，都会占用更多的内存空间以保存其局部变量的附加副本。如果这个进程无限持续下去，最终会导致StackOverflowException错误。

　　效率。几乎在任何情况下都可以用循环替代递归。循环不会产生传递变量、初始化附加存储空间和返回值所需的开销，因此使用循环相对于使用递归调用可以大幅提高性能。

　　相互递归。如果两个过程相互调用，可能会使性能变差，甚至产生无限循环。此类设计所产生的问题与单个递归过程所产生的问题相同，但更难检测和调试。

　　调用时使用括号。当Function过程以递归方式调用它自身时，您必须在过程名称后加上括号（即使不存在参数列表）。否则，函数名就会被视为表示函数的返回值。

　　测试。在编写递归过程时，应非常细心地进行测试，以确保它总是能满足某些限制条件。您还应该确保不会因为过多的递归调用而耗尽内存。