遞歸轉非遞歸的思路和例子

某些算法邏輯，用遞歸很好表述，程序也很好寫。理論上所有的遞歸都是可以轉換成非遞歸的。如果有些場合要求不得使用遞歸，那就只好改成非遞歸了。

通常改成非遞歸算法的思路，就是使用臨時的一個棧來存放計算的臨時值。

下面演示2個例子。

示例一：

假設有如下的遞歸函數

f(1)=3

f(2)=11

f(n)=4*f(n-1)-f(n-2)

那么寫成代碼，這個遞歸函數就是如下：

static int f(int x)
        {
            if (x == 1)
                return 3;
            else if (x == 2)
                return 11;
            else
                return 4 * f(x - 1) - f(x - 2);
        }

如果改寫成非遞歸，那么肯定是要用到循環。

由于計算第n個值的時候，要用到第n-1和第n-2個值，因此，至少要把這2個值存起來。然后使用的時候這2個值都出棧，計算出第n個值，然后，再把第n-1個值和第n個值入棧，以方便計算第n+1的值。具體代碼如下：

static int f_1(int x)
        {
            Stack<int> s = new Stack<int>();
            for (int i = 1; i <= x; i++)
            {
                if (i == 1)
                    s.Push(3);
                else if (i == 2)
                    s.Push(11);
                else
                {
                    int tmp1 = s.Pop();//棧中至少有2個元素了，出棧后以計算下一個元素
                    int tmp2 = s.Pop();
                    int tmp = 4 * tmp1 - tmp2;
                    s.Push(tmp1);
                    s.Push(tmp);//計算結果入棧
                }
            }
            return s.Pop();//返回棧頂元素
        }

示例二：遍歷二叉樹

二叉樹的先序遍歷，中序遍歷，后序遍歷，通常是遞歸實現的，因為很好理解。此處不再贅述遞歸版本。

假設有一個二叉樹：

先用代碼構造出這棵樹。

#region 節點的定義
class node
{
    public string nodevalue;
    public node leftchild, rightchild;
    public node()
    { }
    public node(string value)
    {
        nodevalue = value;
    }
    public void assignchild(node left, node right)//設定左右孩子
    {
        this.leftchild = left;
        this.rightchild = right;
    }
    public bool hasleftchild//是否有左孩子
    {
        get
        {
            return (leftchild != null);
        }
    }
    public bool hasrightchild//是否有右孩子
    {
        get
        {
            return (rightchild != null);
        }
    }
    public override string ToString()
    {
        return nodevalue;
    }
}
#endregion

***************************

static void Main(string[] args)
      {
          node node_a = new node("a");
          node node_b = new node("b");
          node node_c = new node("c");
          node node_d = new node("d");
          node node_e = new node("e");
          node node_f = new node("f");
          node node_g = new node("g");
          node node_h = new node("h");
          node node_i = new node("i");
          //構造一棵二叉樹
          node_a.assignchild(node_b, node_c);
          node_b.assignchild(node_d, node_e);
          node_c.assignchild(node_f, node_g);
          node_e.assignchild(node_h, node_i);
  }

****************************************

非遞歸版本實現先序遍歷。

//先序遍歷
 static void preorder_visit_1(node root)
        {
            Stack<node> s = new Stack<node>();
            s.Push(root);//先序遍歷。首先訪問的是根結點，把根節點放入棧中
            while (s.Count > 0)
            {
                node r = s.Pop();//當前要訪問的結點出棧。
                Console.Write(r.nodevalue);
                //先序遍歷的順序是根，左，右。
                //由于棧的先入后出的特性，因此先插入右孩子，后插入左孩子，能保證取出來的時候是先左后右
                if (r.hasrightchild) //如果有右孩子，則右孩子入棧
                {
                    s.Push(r.rightchild);
                }
                if (r.hasleftchild)//如果有左孩子，則左孩子入棧
                {
                    s.Push(r.leftchild);
                }
            }
        }
//中序遍歷
 static void inorder_visit_1(node root)
        {
            Stack<node> s = new Stack<node>();
            s.Push(root);
            while (s.Count > 0)
            {
                while (s.Peek() != null && s.Peek().hasleftchild)//把該節點的左子樹全部遍歷。
                    //如果s.Peek()==null,說明棧中null下的元素的左孩子已經遍歷過了，該訪問null下的元素本身了。
                {
                    s.Push(s.Peek().leftchild);
                }
                if (s.Peek() == null)
                    s.Pop();
                if (s.Count > 0)
                {
                    var node = s.Pop();
                    Console.Write(node.nodevalue);
                    s.Push(node.rightchild);//如果沒有右子樹，放入空結點
                }
            }
        }