(十三)函数递归
1.堆
在讲函数递归的时候，顺便提一下栈的概念。
堆栈是一种后进先出的推入和弹出数据结构。当程序运行时，系统一次将一个对象推入堆栈，然后堆栈指针下移一个位置。当系统从堆栈中弹出一个对象时，会弹出最近被推入堆栈的对象。然后堆栈指针上移一个位置。程序员经常使用堆栈作为一种数据结构来处理用LIFO逻辑最好描述的编程问题。这里讨论的程序中的堆栈存在于每个程序中。它不需要程序员写代码来维护，而是由正在运行的系统自动处理。所谓系统自动维护，其实就是编译器生成的程序代码。虽然你在源代码中看不到它们，但是程序员应该对它们有所了解。
让我们来看看程序中的堆栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统会将调用者的所有参数和返回地址推入堆栈，堆栈指针会移动到适当的位置来容纳这些数据。堆栈上的最后一个是调用者的返回地址。当被调用方开始执行时，系统将被调用方的参数推入堆栈，并再次向下移动堆栈指针，以确保有足够的空空间来存储被调用方声明的所有参数。当调用方将参数推入堆栈时，被调用方在堆栈中以独立变量的形式建立一个参数。被调用方内部的其他参数也存储在堆栈中。作为这些推送操作的结果，堆栈指针已经移动到所有这些局部变量之下。但是，被调用方在其执行开始时记录了初始堆栈指针，并将其用作访问堆栈中具有正或负偏移值的变量的引用。当被调用者准备返回时，系统弹出堆栈中的所有参数。此时堆栈指针移动到被调用者刚刚开始执行的位置。然后被调用者返回，系统从堆栈中弹出返回地址，调用者可以继续执行。当调用方继续执行时，系统还会从堆栈中弹出调用方的参数，因此堆栈指针会返回到调用发生前的位置。
可能初学者无法理解上面的解释。堆栈涉及指针问题。具体请看一些数据结构的书。想学好编程语言，就必须学习数据结构。
第二，递归
递归是函数实现中非常重要的一个环节，很多程序或多或少都会用到递归函数。递归是指函数调用自己，或者在自己函数调用的从属函数中调用自己。
递归之所以能够实现，是因为函数的每个执行过程在堆栈中都有自己的形参和局部变量的副本，而这些副本与函数的其他执行过程无关。这种机制是大多数编程语言实现子程序结构的基础，它使递归成为可能。假设一个调用函数调用一个被调用函数，然后假设被调用函数反过来调用调用函数。这第二次调用被称为调用函数的递归，因为它发生在调用函数的当前执行过程完成之前。而且由于原调用函数和当前被调用函数在栈的较低位置都有一组独立参数和独立变量，所以原参数和变量不会受到影响，所以递归可以正常工作。程序遍历这些函数的过程称为递归下降。
程序员需要保证递归函数不会任意改变静态变量和全局变量的值，避免上级函数在递归下降过程中出错。程序员还必须确保有一个终止条件来结束递归下降过程，返回到顶级。
例如，这样的程序是递归的:
void a(int)；
主()
{
int num = 5；
a(数字)；
}
void a(整数)
{
if(num==0)返回；
printf(%d，num)；
a(-num)；
}
在函数A()中，你又调用了自己，也就是你调用了自己。这就是递归。那么可能有人会想，这不是死循环吗？所以在递归函数中，必须有一个return语句，没有return语句的递归函数就是无限循环。
我们分析上面的例子，先调用a(5)，然后输出5，再在函数中调用自己a(4)，然后回到函数的起点，输出4，…，直到调用一个(0)。这时候我们发现if条件已经满足，不调用而是返回。因此，这种递归总共执行了五次。没有这个返回，一定是一个死循环。
虽然递归并不难理解，但是使用很多递归函数的时候会出现很多问题。一般有两个原因:一是如何递归下去，就是不知道如何取一个变量递归下去；第二，不知道怎么停止递归，经常会出现无限循环。
看看下面的例子:
1.求1 2 …… 100的和
先分析一下。对于第一个递归变量的问题，变量1，2，…，100应作为递归条件；二是如何终止的问题。从题目来看，应该是数字100的时候，加不下来。那我们试着写程序吧。
int add(int)；
主()
{
int num=1，sn；
sn = add(num)；
printf(%d\\n，sn)；
getch()；
}
int add(int num)
{
静态int序号；
sn = num
if(num==100)返回sn；
添加(数字)；
}
分析程序:先调用add(1)，然后在子函数中把这个1加到sn上。然后调用add(2)，再把sn加到2。这一直到100。到了100，先加起来，然后发现满足if条件。此时返回sn的值，即1 ^ 2…100的值。
这里有个问题必须注意，就是静态int sn
有人不理解为什么用静态类型修饰符，为什么不用int sn = 0；？如果使用int sn = 0；在这样的语句中，每次调用函数add()时，sn的值都赋为0，也就是说，虽然第一步加了1，但在第二次调用时，sn返回0。我们前面说过，static可以保证这次初始化的值是上次执行后的值，从而保证我们之前想加的结果不会丢失。如果修改为int sn=0，最终结果一定是最后一个值100而不是5050。
2.求数列s(n)=s(n-1) s(n-2)的第n项。其中s(1)=s(2)=1。
可以看出，终止条件一定是s(1)=s(2)=1。递归下降的参数必须是n。
int a(int)；
主()
{
int n，s；
scanf(%d，