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