栈与递归

　　函数的递归调用和普通函数调用是一样的，当程序执行到某个函数时，将这个函数进行入栈操作，在入栈之前，通常需要完成三件事。

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

　　2、为被调函数的局部变量分配存储区。

　　3、将控制转移到北调函数入口。

当一个函数完成之后会进行出栈操作，出栈之前同样要完成三件事。

　　1、保存被调函数的计算结果。

　　2、释放被调函数的数据区。

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

上述操作必须通过栈来实现，即将整个程序的运行空间安排在一个栈中。每当运行一个函数时，就在栈顶分配空间，函数退出后，释放这块空间。所以当前运行的函数一定在栈顶。

（注：摘自严蔚敏等人的数据结构c语言版）

 

接下来我们来观察一个简单的递归。

 

#include <stdio.h>

void recurrence(int num)      //被调函数
{
    if ( num < 0 )
        return;
    printf("%d\n", num);
    recurrence(num - 1);     //递归调用函数recurrence（）
　　 printf("%d\n", num);
} 
int main() 
{ 
    recurrence(5); //调用recurrence（）函数
    return 0; 
}

程序每次运行到recurrence()函数时都会进入这个这个函数，直到num<0, 为-1时返回，返回之后会接着运行recurrence()后面的代码，箭头代表函数控制权转移，请看图示。