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

創(chuàng)新互聯(lián)主要為客戶(hù)提供服務(wù)項(xiàng)目涵蓋了網(wǎng)頁(yè)視覺(jué)設(shè)計(jì)、VI標(biāo)志設(shè)計(jì)、營(yíng)銷(xiāo)推廣、網(wǎng)站程序開(kāi)發(fā)、HTML5響應(yīng)式成都網(wǎng)站建設(shè)、手機(jī)網(wǎng)站制作設(shè)計(jì)、微商城、網(wǎng)站托管及網(wǎng)站維護(hù)、WEB系統(tǒng)開(kāi)發(fā)、域名注冊(cè)、國(guó)內(nèi)外服務(wù)器租用、視頻、平面設(shè)計(jì)、SEO優(yōu)化排名。設(shè)計(jì)、前端、后端三個(gè)建站步驟的完善服務(wù)體系。一人跟蹤測(cè)試的建站服務(wù)標(biāo)準(zhǔn)。已經(jīng)為效果圖設(shè)計(jì)行業(yè)客戶(hù)提供了網(wǎng)站開(kāi)發(fā)服務(wù)。

通常改成非遞歸算法的思路，就是使用臨時(shí)的一個(gè)棧來(lái)存放計(jì)算的臨時(shí)值。

下面演示2個(gè)例子。

示例一：

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

f(1)=3

f(2)=11

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

那么寫(xiě)成代碼，這個(gè)遞歸函數(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);
        }

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

由于計(jì)算第n個(gè)值的時(shí)候，要用到第n-1和第n-2個(gè)值，因此，至少要把這2個(gè)值存起來(lái)。然后使用的時(shí)候這2個(gè)值都出棧，計(jì)算出第n個(gè)值，然后，再把第n-1個(gè)值和第n個(gè)值入棧，以方便計(jì)算第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個(gè)元素了，出棧后以計(jì)算下一個(gè)元素
                    int tmp2 = s.Pop();
                    int tmp = 4 * tmp1 - tmp2;
                    s.Push(tmp1);
                    s.Push(tmp);//計(jì)算結(jié)果入棧
                }
            }
            return s.Pop();//返回棧頂元素
        }

示例二：遍歷二叉樹(shù)

二叉樹(shù)的先序遍歷，中序遍歷，后序遍歷，通常是遞歸實(shí)現(xiàn)的，因?yàn)楹芎美斫?。此處不再贅述遞歸版本。

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

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

#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)造一棵二叉樹(shù)
          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);//先序遍歷。首先訪(fǎng)問(wèn)的是根結(jié)點(diǎn)，把根節(jié)點(diǎn)放入棧中
            while (s.Count > 0)
            {
                node r = s.Pop();//當(dāng)前要訪(fǎng)問(wèn)的結(jié)點(diǎn)出棧。
                Console.Write(r.nodevalue);
                //先序遍歷的順序是根，左，右。
                //由于棧的先入后出的特性，因此先插入右孩子，后插入左孩子，能保證取出來(lái)的時(shí)候是先左后右
                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)的左子樹(shù)全部遍歷。
                    //如果s.Peek()==null,說(shuō)明棧中null下的元素的左孩子已經(jīng)遍歷過(guò)了，該訪(fǎng)問(wèn)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);//如果沒(méi)有右子樹(shù)，放入空結(jié)點(diǎn)
                }
            }
        }

文章名稱(chēng)：遞歸轉(zhuǎn)非遞歸的思路和例子
轉(zhuǎn)載源于：http://chinadenli.net/article2/giohic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、品牌網(wǎng)站制作、網(wǎng)站改版、網(wǎng)站內(nèi)鏈、自適應(yīng)網(wǎng)站、云服務(wù)器

廣告

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