【连载】（堆栈和递归函数）乐创DIY C语言讲义——4.5节

4.5 堆栈和递归函数

堆栈这个概念，最早学习微机原理的时候就学过，它表示的是一种在汇编语言调用子程序时候保存现场的存储空间，它所具有的数据结构属性就是先进后出，这个是我们之前学习计算机硬件时候讲述的堆栈概念。

但是在计算机软件中，堆栈的表示的含义可不仅仅是一个存储空间了，在计算机软件中，一般将堆栈分开来解释。一般地，在C/C++语言的体系内，一块计算机的内存被分为以下几种存储空间。

²栈区（stack）：由编译器自动分配释放，存放函数的参数名，局部变量的名等。其操作方式类似于数据结构中的栈。

²堆区（heap）：由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。

²静态区（static）：全局变量和局部静态变量的存储是放在一块的。程序结束后由系统释放。

²文字常量区：常量字符串就是放在这里的，程序结束后由系统释放。

²程序代码区：存放函数体的二进制代码。

由此可知，我们之前程序中定义的变量，都是利用“int 变量名”这种方式去定义的，这种方式定义的变量，其实它前面隐藏了一个C语言中可有可无的关键词“auto”，这个关键词是C语言中最没有存在感的，当然它也都是以隐形的形象“展示”在世人面前的。以上的变量定义，如果我们把auto展示出来就是“auto int 变量名”，其实这里的auto表示的就是自动存储的变量，除此以外还有register，extern，static等关键词来指定变量的存储类型。一般地，用“auto”声明的局部变量，其存储类型为栈存储，即编译器在函数调用时自动分配，函数退出后自动回收。用“static”定义的局部变量和全局变量都被存放在静态区，这些静态区的变量，一旦定义好就不会被回收，除非程序终结，由操作系统（无操作系统时，硬件释放）。而如果你想把数据存储在堆区，是需要事先申请，申请成功之后，才可以操作堆区来存放代码，堆区的代码是需要手动释放的，这个后面我们来说。

以上是关于C语言变量存储和堆栈的简述。接下来，我们将会讨论到的是递归函数。很多书上的递归函数是基于阶乘计算和斐波那契数列的例子来讲的，但是《C与指针》的作者Kenneth早就阐述了这两个例子不好的原因：第一个例子，阶乘明明使用for循环方便得多，无需去使用递归，第二个例子，斐波那契数列，用递归计算，它的效率是低下的是非常恐怖的。因此，我们采用一个与众不同的例子。有做过单片机数码管显示数字的同学都知道，要把一个数字如“4567”显示在一个四位的数码管上，是一件非常头疼的事情，你需要通过十进制取余和取模的方式，一位一位分离出来，但是使用递归，只需要一个简单的函数即可。

在此之前，我们先来说明一下什么叫“递归函数”。函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。看不懂没关系，现在你的认识可以理解在一个函数中调用这个函数它自己本身的函数叫做递归函数。

先看上面所说的例子，有一个数字“4567”，利用递归函数将其一位一位剥离出来，分别输出数字“4”，“5”，“6”，“7”。其代码如图4-5-1所示。

图4-5-1 递归函数剥离每一位

关于递归函数，这一节就先写到这里，为了内容的完整才写了这一节，由于数组等高级数据结构还没讲述，先把这个问题留下，等后面再来详细阐述。