递归函数

• 一、基本的递归函数

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

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

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

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

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

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

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