一尾递归
以下是具体实例:
线性递归:
long Rescuvie(long n) {
return(n == 1) ? 1 : n * Rescuvie(n - 1);
}
尾递归:
long TailRescuvie(long n, long a) {
return(n == 1) ? a : TailRescuvie(n - 1, a * n); //尾递归发生时，父函数的活动记录已经不会再被用到，可以直接被该尾递归的子函数覆盖。
}
long TailRescuvie(long n) {//封装用的
return(n == 0) ? 1 : TailRescuvie(n, 1);
}
尾递归可以变成迭代。
二递归问题栈化
递归问题非递归化的主要方式是栈模拟递归过程。优点是减少了函数调用的cpu开销。
我们先从周游讲起吧。
后序周游
先看一段伪码：
xx=dfs（ele）{
//tag=0
dfs(ele->left)
//tag=1
dfs(ele->right)
//tag=2
dosth(ele)
//finish
}
典型的后序周游 （原题见leetcode）：
正常人会这么写：
class Solution {
public:
// 非递归版本
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
typedef pair<TreeNode *, int> Pair;
stack<Pair> ss;
if(root) /////@@@error if no
ss.push(Pair(root, 0));
while(!ss.empty()){
Pair &p = ss.top();
TreeNode *root = p.first;
if(p.second==0){//tag=0 （刚进入该函数，左右子树尚未被访问）
while(root->left){//先访问左子树
ss.push(Pair(root->left, 1));
root=root->left;
}
p.second = 1;// 标记再次遇到该节点的时候它的左子树已经被访问过
}else if(p.second==1){//tag=1 (这个节点左子树已经被访问过)
if(root->right){
ss.push(Pair(root->right, 0)); //先访问右子树
}
p.second=2; // 标记再次遇到该节点的时候它的右子树已经被访问过
}else{ // tag=2 (这个节点的右子树已经被访问过）
res.push_back(root->val);
ss.pop(); //访问节点结束
}
}
return res;
}
/* 递归版本1 不带返回值 */
vector<int> post1(TreeNode *root){
vector<int> res;
dfs(res, root);
return res;
}
void dfs(vector<int> &cur, TreeNode *root){
// tag=0
if(!root) return;
if(root->left) dfs(cur, root->left);
// tag=1
if(root->right) dfs(cur, root->right);
// tag=2
cur.push_back(root->val);
}
/* 递归版本2 带返回值 */
vector<int> postorderTraversal(TreeNode *root) {
vector<int> c;
if(root==NULL) return c;
vector<int> a=postorderTraversal(root->left);
vector<int> b=postorderTraversal(root->right);
c.insert(c.end(),a.begin(),a.end());
c.insert(c.end(),b.begin(),b.end());
c.insert(c.end(),root->val);
return c;
}
};
其中上一个函数就是用的非递归，用了一个站，模拟递归。下一个函数是递归版本。
模拟的思路无非是给ele赋予一个标记tag，tag设定为从第i个dfs分支返回（状态 i=1~n ）或刚进入（状态 0）
对于后序周游，tag=0，1, 2 分别指代 第一次遇到该节点，再次遇到该节点的时候它的左子树已经被访问过，再次遇到该节点的时候它的右子树已经被访问过
中序周游
那么中序周游怎么写非递归呢？（原题见 leetcode）：
首先是递归版本：
dfs（ele）： dfs(ele->left) dosth(ele) dfs(ele->right)
然后是去递归：
普通做法：
xx(ele){
//tag=0
dfs(ele1)
//tag=1
dosth(ele)
dfs(ele2)
//finished
}
上述tag其实还可以减少一个，变成一个（不需要了）：
xx(ele){
while...push(ele1) //dfs -> while
//tag=0
dosth(ele)
dfs(ele2)
}
中序很好非递归化， 每个元素访问之前先把左子节点依次加入栈中，这样以来 下次遇到该节点的时候左子树已经被访问过，
直接访问该节点，并把右子节点以及其左子节点依次加入栈中。
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode *> ss;
while(root){ ss.push(root); root=root->left; }
while(!ss.empty()){
TreeNode *p = ss.top(); ss.pop(); // p's left-child has been visited
res.push_back(p->val);
if(p->right){
TreeNode *q=p->right;
while(q){ ss.push(q); q=q->left; }
}
}
return res;
}
};
前序周游
前序同样：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode *> ss;
vector<int> res;
while(root){
while(root){ res.push_back(root->val); ss.push(root); root = root->left; } //依次访问自身和左子节点
root = NULL;
while(!ss.empty()){ // 再次遇到节点p
TreeNode *p = ss.top(); ss.pop();
if(p->right) {
root=p->right; // 试图访问p的右子节点
break;
}
}
}
return res;
}
};
或者：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode *> ss;
vector<int> res;
// 第一次遇到节点 root：依次访问右子节点和其左子节点
while(root){ res.push_back(root->val); ss.push(root); root = root->left; }
// 从栈中找到一个结点p（再次遇到节点p），由于其及其左子树已经访问过， 所以访问其右子树
while(!ss.empty()){
TreeNode *p = ss.top(); ss.pop();
if(p->right) {
root=p->right; // 访问p的右子树
while(root){ res.push_back(root->val); ss.push(root); root = root->left; } //第一次遇到节点p->right：依次访问其和其左子节点
}
}
return res;
}
};
前序和中序比后序简单，因为其中一个dfs（对左子节点的访问）可以合并到一个操作（while循环）中。
为什么这个左子节点对应的dfs分支可以合并到while呢？因为他是父dfs里第一个操作，相当于一个迭代。所以遇到一个dfs节点，二话不说先依次把左子节点依次压栈，就完成了左dfs分支。这么一来，减少了一个需要用栈模拟的dfs分支。
于是我们用对左子树操作合并到while循环的方法，改进后序周游
后序周游改进版
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
typedef pair<TreeNode *, int> Pair;
stack<Pair> ss;
while(root){ ss.push(Pair(root, 0)); root=root->left; }
while(!ss.empty()){
Pair &p = ss.top();
TreeNode *root = p.first;
if(p.second==0){
//右子树未被访问，现在访问
if(root->right){
root=root->right;
while(root){ ss.push(Pair(root, 0)); root=root->left; }
}
//访问完右子树
p.second=1;
}else{
//左子树显然被访问过， 而p.second=1, 所右子树也被访问过
//访问自己
res.push_back(root->val);
ss.pop(); //访问完成
}
}
return res;
}
};
进一步改进
重新考虑dfs：
xx(ele){
dosth1
//tag = 0
dfs(ele1)
//tag=1
dostr2
dfs(ele2)
// tag=2
....
}
以上是比较复杂的dfs
但是后序周游是很简单的：
xx(ele){
// tag=0
dfs(ele1)
// tag=1
dfs(ele2)
// tag=2
dosth
}
注意到两个相邻的dfs之间没有操作（dosth），这意味着他们可以一次性入栈，中间不用加tag（强调tag代表从第几个分支返回状态 i 或刚进入状态 0）。
所以上述过程可以改进成下面的：
xx(ele){
// tag=0
dfs(ele1)
dfs(ele2)
// tag=1
dosth
}
为什么可以上述优化？因为dfs(ele1)和dfs（ele2）是挨在一起，可以连续入栈，所以省去了一个tag。注意入栈顺序和dfs顺序相反，先入right，再入left：
void post_travel(Node *root){
stack<Pair> ss;
ss.push(Pair(root, 1));
while(!ss.empty()){
Pair &p = ss.top();
Node*q=p.first;
if(p.second==0){//tag==0
ss.push(Pair(q.right, 0)),
ss.push(Pair(q. left, 0));
p.second=1;
}else{//tag==1
dosth(q);
ss.pop();//finish
}
}
于是发现前序周游也可以被改进：
xx(ele){
//tag=0
dosth(ele)
dfs(ele1)
dfs(ele2)
//finish
}
void pre_travel(Node *root){
stack<Pair> ss;
ss.push(root);
while(!ss.empty()){
Pair &p = ss.top();
Node*q=p.first;
dosth(q)
ss.pop(); //finish visit root, won't return again so no need keep it in the stack
ss.push(q.right),
ss.push(q. left);
}
}
总结
于是总结发现，递归转非递归，
要处理好 1 第一次遇到ele 2 再次遇到ele（从栈顶访问到ele） 3 乃至第n次遇到ele（第n-1次从栈顶访问到ele）
当n>2时， 需要在栈中标记ele访问次数。如后序周游的tag的那样。