C语言：数据结构-栈与递归

栈的一个重要应用是在程序设计语言中实现递归。所谓递归，是指如果一个对象部分地包括它自己，或用它自己给自己定义，则称这个对象是递归的，或定义为在一个过程中直接或间接地调用自己，则称这个过程是递归的。在调用一个函数（程序）的过程中又直接或间接地调用该函数（程序）本身，称为函数的递归调用。一个递归的求解问题必然包含终止递归的条件，当满足一定条件时就终止向下递归，从而使问题得到解决。描述递归调用过程的算法称为递归算法。在递归算法中，需要根据递归条件直接或间接地调用算法本身，当满足终止条件时结束递归调用。

现实中有许多实际问题采用递归方法来解决，使用递归的方法编写程序将使许多复杂的问题大大简化。例如计算求n的阶乘问题，可以利用阶乘的递推公式n!=n*(n-1)!，对该问题进行分解，把计算n的阶乘问题化为等式右边涉及规模较小的同类问题(n-1)的阶乘的计算。

例用递归函数求解正整数n的阶乘（n!）

设f(n)=n!，则递归函数f(n)可表示为：

此处n=0为递归终止条件，使函数返回1；当n>0时实现递归调用，由n的值乘以f(n-1)的返回值求出f(n)的值。

上述递归函数用c语言描述为：

int f(int n) { if(n==0) return 1; else return n*f(n-1); }

可见，递归算法设计的原则是用自身的简单情况来定义自身，使其一步比一步更简单，直至终止条件。设计递归算法的方法是：

（1）寻找递归的通式，将规模较大的原问题分解为规模较小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题（例如n!=n*(n-1)!）。

（2）设置递归出口，确定递归终止条件（例如求解n!时，当n=0时，f(0)=1）。

上述求阶乘的递归函数中，假设n=4，递归函数f(4)的调用和返回过程如图3-4所示。

求解f（4）的过程

从图3-4可知，求解f(4)的值分为递归和返回求解两个阶段，在递归阶段，每一次调用f(n)函数时，并不是立即得到f(n)的值，而是一次一次地进行递归调用，即求f(4)需递归调用f(3)，而f(3)无法求得，进而需要调用f(2)，依次类推，直到f(0)有确定值时，递归不再进行，然后开始返回求解阶段。递归终止时，f(0)=1，由此可求出1*f(0)=1为f(1)的返回值，再由f(1)的值求出2*f(1)=2*1=2，作为f(2)的返回值。依次返回求解，最后递推出f(4)=24。

递归函数调用时，是按照“后调用先返回”的原则处理调用过程，如上述求阶乘的递归函数调用，最后调用的是f(0)，因而最先返回f(0)的值。因此执行递归函数是通过具有后进先出性质的栈来实现的。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时就为它在栈顶分配一个存储空间，而每当从一个函数退出时，就释放它的存储区。