递归函数非递归化_2示例

某些算法逻辑，用递归很好表述，程序也很好写。理论上所有的递归都是可以转换成非递归的。
如果有些场合要求不得使用递归，那就只好改成非递归了。通常改成非递归算法的思路，就是使用一个栈来存放计算的临时值。

下面通过2示例展示递归函数非递归化：
示例一： f(n) = 4*f(n-1) - f(n-2)
示例二：二叉树遍历 之 先序遍历 和 中序遍历 


示例一：
假设有如下的递归函数
f(1)=3
f(2)=11
f(n)=4*f(n-1)-f(n-2)
那么写成代码，这个递归函数就是如下：

// 递归实现
int f_rec(int n)
{
    int res;
    if(n == 1)
            res = 3;
    else if(n==2)
            res = 11;
    else
            res = 4*f_rec(n-1)-f_rec(n-2);
    cout<<"f_rec("<<n<<")="<<res<<endl;
    return res;
}

递归函数非递归实现，需要使用循环。
“递归方式求 f(n) 需要使用 f(n-1)和f(n-2)” 改为非递归则变成 “已知 f(n-2)和f(n-1) 则可计算 f(n)”。
已知条件是 f(1)=3,f(2)=11，循环计算直到参数为n。

// 非递归实现1
int f_flat1(int n)
{
    int res;
    int i;
    int fn_2 = 3;  // 已知f(n-2)
    int fn_1 = 11; // 已知f(n-1)


    if (n == 1)
        res = 3;
    else if (n == 2)
        res = 11;
    else {
        for (i = 3; i <= n; i++) {
            res = 4 * fn_1 - fn_2;  // 计算f(n)
            printf("f(%d)=4*%d-%d=%d\n",
                            i, fn_1, fn_2, res);
            fn_2 = fn_1;
            fn_1 = res;
        }
    }

    return res;
}

// 非递归实现2
int f_flat2(int n)
{
    int res;
    stack<int> st;
    int i;

    st.push(3);
    st.push(11);
    for(i=3; i<=n; i++)
    {
            int fn_1 = st.top(); // 已知 f(n-1)
            st.pop();
            int fn_2 = st.top(); // 已知 f(n-2)
            st.pop();
            res = 4*fn_1 - fn_2; // 计算 f(n)
            printf("f(%d)=4*%d-%d=%d\n",
                            i, fn_1, fn_2, res);
            st.push(fn_1);
            st.push(res);
    }
    res = st.top();

    return res;
}

//测试
int main()
{
        int res;
        int n = 5;
        res = f_rec(n);
    //    res = f_flat1(n);
    //    res = f_flat2(n);
    cout<<"result:"<<res;

    return 0;
}

递归版本的计算过程: 
rec_fun(2)=11
rec_fun(1)=3
rec_fun(3)=41
rec_fun(2)=11
rec_fun(4)=153         // f(n-1)
rec_fun(2)=11
rec_fun(1)=3
rec_fun(3)=41           // f(n-2)
rec_fun(5)=571            // f(n)
result:571
计算 f(n) 需要先计算 f(n-1)和f(n-2)，它们的计算也都是递归，因此有重复计算。

非递归版本的计算过程：
f(3)=4*11-3=41
f(4)=4*41-11=153
f(5)=4*153-41=571
result:571

---

示例二：遍历二叉树
二叉树的先序遍历，中序遍历，后序遍历，通常是递归实现的，很好理解。
假设有一个二叉树：
A->{B,C}
B->{D,E}
C->{F,G}
E->{H,I}


先用代码构造出这棵树，然后遍历之。

class node{
public:
    string value;
    node *lchild, *rchild;
    node(){}
    node(string val)
    {
        value = val;
        lchild = NULL;
        rchild = NULL;
    }
    void assignChild(node *left, node *right)
    {
        lchild = left;
        rchild = right;
    }
    bool hasLeftChild()
    {
        return lchild != NULL;
    }
    bool hasRightChild()
    {
        return rchild != NULL;
    }

}

void travalFirst_rec(node *root);
void travalmiddle_rec(node *root);
void travalFirst_flat(node *root);
void travalmiddle_flat(node *root);
int main()
{
    node nA("a");
    node nB("b");
    node nC("c");
    node nD("d");
    node nE("e");
    node nF("f");
    node nG("g");
    node nH("h");
    node nI("i");
    nA.assignChild(&nB, &nC);
    nB.assignChild(&nD, &nE);
    nC.assignChild(&nF, &nG);
    nE.assignChild(&nH, &nI);

    // traval
    cout<<"traval first:"<<endl;
    travalFirst_rec(&nA);
    cout<<"\ntraval middle:"<<endl;
    travalmiddle_rec(&nA);
    cout<<"\ntraval first_flat:"<<endl;
    travalFirst_flat(&nA);
    cout<<"\ntraval middle_flat:"<<endl;
    travalmiddle_flat(&nA);
return 0;
}

// 先序遍历_递归实现
void travalFirst_rec(node *root)
{
    if(root==NULL)
            return;
    // visit first
    cout<<root->value<<endl;
    if(root->hasLeftChild())
        travalFirst_rec(root->lchild);
    if(root->hasRightChild())
        travalFirst_rec(root->rchild);
}

// 中序遍历_递归实现
void travalmiddle_rec(node *root)
{
    if(root==NULL)
            return;
    if(root->hasLeftChild())
        travalmiddle_rec(root->lchild);
    // visit second
    cout<<root->value<<endl;
    if(root->hasRightChild())
        travalmiddle_rec(root->rchild);
}

// 先序_非递归实现
// 对于子树：先访问根结点，再访问左子树，然后访问右子树。
// 访问根结点后，用栈把右子树保存，访问完左子树后再访问右子树。因为对于左子树也这这个过程，所以前面将右子树入栈时，把左子树也入栈，然后开始下一个循环。
void travalFirst_flat(node *root)
{
    stack<node *> st;
    node *nd, *ln, *rn;

    if(root == NULL)
            return;
    st.push(root);
    while(!st.empty())
    {
        nd = st.top();
        st.pop();
        cout<<nd->value<<endl;

        // due to stack's FILO character, "push right child before right child" makes "pop left child before right child"
        if(nd->hasRightChild())
                st.push(nd->rchild);
        if(nd->hasLeftChild())
                st.push(nd->lchild);
    }
}

// 中序_非递归实现
// 先访问左子树，再访问根结点，最后是右子树。
// 对于左子树也是这个过程。所以对于子树，先访问的是最左结点，从根到最左结点之间的所有结点都入栈。
// 访问完最左结点，再访问其父结点，最后是右子树。怎样访问右子树呢？这是递归过程，非递归化后当然是在下一次循环中处理。
void travalmiddle_flat(node *root)
{
    stack<node *>st;
    node *nd, *ld, *rd;
    st.push(root);

        // push left edge
        do {
            nd = st.top();
            cout<<"push left child for:"<<nd->value<<endl;
            if(nd->hasLeftChild())
                    st.push(nd->lchild);
            else
            {
                cout<<"no left child for:"<< nd->value<<endl;
                break;
            }
        }while(1);

    while(!st.empty())
    {
        // pop and visit most left node
        nd = st.top();
        st.pop();
        cout<<nd->value<<endl;
        // push right child
        if(nd->hasRightChild())
        {
            cout<<"push right child for:"<<nd->value<<endl;
                st.push(nd->rchild);
        // push left edge
        do {
            nd = st.top();
            cout<<"push left child for:"<<nd->value<<endl;
            if(nd->hasLeftChild())
                    st.push(nd->lchild);
            else
            {
                cout<<"no left child for:"<< nd->value<<endl;
                break;
            }
        }while(1);
        }
        else
        {
            cout<<"no right child for:"<< nd->value<<endl;
        }
    }
}

递归和非递归实现
先序遍历和中序遍历过程：

traval first:
a
b
d
e
h
i
c
f
g


traval middle:
d
b
h
e
i
a
f
c
g


traval first_flat:
a
b
d
e
h
i
c
f
g


traval middle_flat:
push left child for:a
push left child for:b
push left child for:d
no left child for:d
d
no right child for:d
b
push right child for:b
push left child for:e
push left child for:h
no left child for:h
h
no right child for:h
e
push right child for:e
push left child for:i
no left child for:i
i
no right child for:i
a
push right child for:a
push left child for:c
push left child for:f
no left child for:f
f
no right child for:f
c
push right child for:c
push left child for:g
no left child for:g
g
no right child for:g

---

如果你动手实践以上代码，你会可能遇到2个问题：
1、包含哪些头文件
2、怎样编译
这2个示例的头文件和Makefile都是一样的（我在Cygwin上编译）

#include <iostream>
#include <stack>

using namespace std

srcs=main.cpp
objs=$(srcs:.c=.o)
CC=g++

all: a test

a: $(objs)
    $(CC) -o $@ $^
%.o: %.c
    $(CC) -c $^ -o $@

clean:
    rm -f *.o
    rm -f a

test:
    ./a

下面是非递归化需要使用的数据结构
std::stack::top - cppreference.com

REF:
http://blog.chinaunix.net/uid-29052194-id-3869354.html

Update:
2013-8-29