学步园

• 一、基本的递归函数

      首先先来了解下C程序在内存中的组织方式，基本上来说一个可执行的程序在内存中有4个区域组成：代码段、静态数据区、堆与栈。代码段包含程序运行时所执行的机器指令；静态数据区是包含在程序的生命周期内的一直持续的数据，比如全局变量和静态的局部变量；堆包含程序运行过程中动态分配的存储空间。栈是函数调用过程中所使用的信息。

       当C程序调用一个函数，栈会分配一个空间来保存与这个调用相关的信息。每一个调用都被当作是活跃的，栈上的那块存储区域成为活跃记录，或者叫栈帧。栈帧有5个区域组成。如下图

           下面以最简单的阶乘例子来讲介基本递归的实现过程：

• 例子：F（n)=nF(n-1) 当n =1或者0时，F（n) =1;

   下图展示了利用递归的方法计算的4！过程，描述了递归过程的2个阶段：递推和回归。在递推阶段，每个递归调用自己来记住这次递归的过程，当其中有一个递归条件结束时，递推结束；进入回归阶段！也就是说，递归函数必须拥有一次终止的条件；否则，递归函数无法结束。

   每次函数调用都是一个活跃记录信息，而栈是存储信息的。每个活跃记录都占有栈的一定存储空间，而这些函数调用只有到终止条件时，才能逐个释放栈的空间。因此生成和释放活跃记录都需要一定的时间，这样函数调用的开销很大。如果当函数调用太长的话，很容易造成栈溢出，从而出现问题，这样我们便引进来了另一种递归叫为递归。

下面以4！为例描述为递归的过程，很容易为递归每次调用需要一个活跃记录，调用结果会释放活跃记录，进入下一次调用。一直到终止条件。很容易看出为递归比基本递归函数优点。