一、递归函数的实现：

递归函数由操作系统的“系统栈”来实现，在调用另一函数前，操作系统先要：

1、下一条语句的地址入栈，即返回地址入栈：

2、被调用函数的形式参数 入栈，

3、被调用函数的局部变量 入栈

    函数在声明或定义处的参数，称为形参，它实际上位于栈内的某个内存地址。至于实参，就是调用时函数时所用的参数，它不在栈内存区里。

   当函数采用传值方式时，即把实在参数在栈中拷贝一份，用作形式参数；当函数采用传址方式时，即把实在参数的地址作为形式参数入栈；当有多个参数时，是参数a还是参数b先入栈，这依编译器而定，大都数编译器采用“从右到左的次序”将参数一个个压入。

当本次函数调用结束后：

1、保存函数返回值 （至通用寄存器EAX中）。 

2、清理堆栈：先将局部变量出栈，再将形式参数出栈。至于由调用函数或被调用函数执行，参见调用约定

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

    C/C++的函数返回值一般是放在寄存器eax里的，而不是在栈里。返回值可以放在栈里，但你在C的语言层面上可能做不到，其实随着函数的结束，mov esp, ebp这条指令过后，函数内部的局部变量就报废了。如果你之后没改变过栈的内容，你可以用栈来存返回值，但比起用寄存器来存储，存储和读取要慢的多。

   Visual C/C++ 的编译器支持如下的函数调用约定：

二、递归的“非递归化”及效率比较

1、用“自定义栈”来实现非递归化

   在“空间效率”上，递归在操作系统中是用系统栈来实现的，当递归很深时，很容易发生系统“栈内存”溢出的危险。当采用“自定义栈”时，可以解决一些“栈内存溢出”的问题，但程序会显得复杂，且难以理解。

在时间效率上：

　　“自定义栈”如果是“手动实现”，即"malloc(); stack[p++]=n;"，省去了返回地址和局部变量出入栈问题，效率会高点；

　　但如果使用标准的stack类(包括模板类的实例），在调用“pop、push”时同样会调用系统栈，即涉及返回地址的出入栈问题。这时只有当递归函数中局部变量很多时效率才会高点，因“自定义栈”不需要存储被调用函数的局部变量。

　　至于递归函数内调用其它函数的多少是无影响的，因为其它函数在开始递归前已结束或未调用。

　　至于消除无效递归，那是程序设计的问题。使用“自定义栈”时可以消除的无效出入栈，在递归中就变成了除无效递归问题。

　　另外说点“栈存储结构“问题，栈一般是使用“顺序栈”而非“链式栈”，因为栈不涉及特定元素的插入、删除操作。而如果使用“链式栈”，在压入和弹出元素时，将会涉及malloc内存分配的问题，效率就大大降低。

  　最后我们也看到，当“递归深度有限”且“递归程序局部变量很少”时，使用递归也个不错的选择，因为代码容易理解，且效率并不低！