一、函数栈
函数的调用过程其实就是一个压栈的过程，在函数栈中，每个函数所占空间成为一个 栈帧。栈帧中保存着函数的形参，返回地址，局部变量，EBP等信息。一个栈帧可以理解为栈的一个元素，函数调用过程是压栈的过程，函数返回则可以简单理解为弹栈的过程。
二、函数栈与递归
栈是一种后进先出的数据结构，函数栈同理。不同的是，栈里面存储的是相同类型的数据，且数据之间相互独立，函数栈每一个栈帧空间内可以存储不同类型的数据，数据之间可以关联。递归的过程就是将相同的函数不断压栈的过程，它们一般操作这同一个数据结构，到达某一特定条件后返回（系统栈空间由操作系统分配，不可能无限大，所以递归调用容易造成栈溢出）。
三、递归实现栈反转
申请额外的数据结构可以很轻松地实现栈反转，但是函数栈本身也是一个栈，也可以当做一个数据结构来使用。
给定一个栈，要求不申请其他数据结构，实现栈的反转。
如给定栈[1, 2, 3] （栈顶到栈底）
返回[3, 2, 1]
这个问题需要两个函数辅助完成，第一个函数得到栈底元素并返回：
int get(stack<int> &s)
{
int result = s.top();
s.pop();
if (s.empty()) {
return result;
} else {
int last = get(s);
s.push(result);
return last;
}
}
以栈 [1, 2, 3] 为例分析此函数递归过程：
- 递归第一层， 得到栈顶元素
1并保存在result中。 - 递归第二层，得到栈顶元素
2并保存在result中。 - 递归第三层，得到栈顶元素
3并保存到result中。此时栈s为空，函数将result返回。 - 函数返回第二层，将第三层返回的
result保存到last中，并将第二层的result（值为2）压回栈s中，返回last 。 - 函数返回第一层，将第二层返回的
last保存到第一层的last中，并将第一层的result（值为1）压栈，最后返回last。
第二个函数将get()函数的返回值压栈，最后取出的值最先压栈，按照get()函数的规则，最后取出的值为1，所以1最先压栈，3最后压栈。
void reserve(stack<int> &s)
{
if (s.empty()) return;
int i = get(s);
reserve(s);
s.push(i);
}
以栈 [1, 2, 3] 为例分析此函数递归过程：
- 递归第一层，调用get函数得到栈底元素
3，保存到i中。 - 递归第二层，调用get函数得到栈底元素
2，保存到i中。 - 递归第三层，调用get函数得到栈底元素
1，保存到i中。 - 递归第四层，栈
s为空，直接返回。 - 函数返回第三层，将元素
1压栈。 - 函数返回第二层，将元素
2压栈。 - 函数返回第一层，将元素
3压栈。
由递归过程看出，栈[1, 2, 3] （栈顶到栈底）已经被反转为[3, 2, 1] （栈顶到栈底）。
这个方法的巧妙之处在于，利用函数栈来存储栈s中弹出的数据，从而避免了申请额外的数据结构。函数栈本身也是一种可利用的“数据结构”。这就好理解为什么可以用递归解决的问题都可以用迭代来解决了。
尽管如此，还是应该尽量少用递归解决问题，因为每一次函数调用都需要申请额外的栈帧空间，这会造成不小的系统开销。虽然函数栈也是可利用的数据结构，但是栈帧里面毕竟存储了太多函数执行过程中需要的信息，如返回地址，EBP等。对空间也是一种浪费。
