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

成都創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)與策劃設(shè)計,天橋網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:天橋等地區(qū)。天橋做網(wǎng)站價格咨詢:18980820575

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

下面演示2個例子。

示例一：

假設(shè)有如下的遞歸函數(shù)

f(1)=3

f(2)=11

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

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

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);
        }

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

由于計算第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);//計算結(jié)果入棧
                }
            }
            return s.Pop();//返回棧頂元素
        }

示例二：遍歷二叉樹

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

假設(shè)有一個二叉樹：

先用代碼構(gòu)造出這棵樹。

#region 節(jié)點(diǎn)的定義
class node
{
    public string nodevalue;
    public node leftchild, rightchild;
    public node()
    { }
    public node(string value)
    {
        nodevalue = value;
    }
    public void assignchild(node left, node right)//設(shè)定左右孩子
    {
        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");
          //構(gòu)造一棵二叉樹
          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);
  }

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

非遞歸版本實(shí)現(xiàn)先序遍歷。

//先序遍歷
 static void preorder_visit_1(node root)
        {
            Stack<node> s = new Stack<node>();
            s.Push(root);//先序遍歷。首先訪問的是根結(jié)點(diǎn)，把根節(jié)點(diǎn)放入棧中
           while (s.Count > 0)
            {
                node r = s.Pop();//當(dāng)前要訪問的結(jié)點(diǎn)出棧。
                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)//把該節(jié)點(diǎn)的左子樹全部遍歷。
                    //如果s.Peek()==null,說明棧中null下的元素的左孩子已經(jīng)遍歷過了，該訪問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);//如果沒有右子樹，放入空結(jié)點(diǎn)
                }
            }
        }

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁標(biāo)題：遞歸轉(zhuǎn)非遞歸的思路和例子-創(chuàng)新互聯(lián)
文章位置：http://chinadenli.net/article48/dhjhhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、關(guān)鍵詞優(yōu)化、服務(wù)器托管、企業(yè)網(wǎng)站制作、品牌網(wǎng)站設(shè)計、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)