转自&＃xff1a;http://blog.51cto.com/cnn237111/1241956
某些算法逻辑&＃xff0c;用递归很好表述&＃xff0c;程序也很好写。理论上所有的递归都是可以转换成非递归的。如果有些场合要求不得使用递归&＃xff0c;那就只好改成非递归了。
通常改成非递归算法的思路&＃xff0c;就是使用临时的一个栈来存放计算的临时值。
下面演示2个例子。
示例一&＃xff1a;
假设有如下的递归函数
f(1)&＃61;3
f(2)&＃61;11
f(n)&＃61;4*f(n-1)-f(n-2)
那么写成代码&＃xff0c;这个递归函数就是如下&＃xff1a;
| 1 2 3 4 5 6 7 8 9 | static int f(int x) { if (x &＃61;&＃61; 1) return 3; else if (x &＃61;&＃61; 2) return 11; else return 4 * f(x - 1) - f(x - 2); } |
如果改写成非递归&＃xff0c;那么肯定是要用到循环。
由于计算第n个值的时候&＃xff0c;要用到第n-1和第n-2个值&＃xff0c;因此&＃xff0c;至少要把这2个值存起来。然后使用的时候这2个值都出栈&＃xff0c;计算出第n个值&＃xff0c;然后&＃xff0c;再把第n-1个值和第n个值入栈&＃xff0c;以方便计算第n&＃43;1的值。具体代码如下&＃xff1a;
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | static int f_1(int x) { Stack<int> s &＃61; new Stack<int>(); for (int i &＃61; 1; i <&＃61; x; i&＃43;&＃43;) { if (i &＃61;&＃61; 1) s.Push(3); else if (i &＃61;&＃61; 2) s.Push(11); else { int tmp1 &＃61; s.Pop();//栈中至少有2个元素了&＃xff0c;出栈后以计算下一个元素 int tmp2 &＃61; s.Pop(); int tmp &＃61; 4 * tmp1 - tmp2; s.Push(tmp1); s.Push(tmp);//计算结果入栈 } } return s.Pop();//返回栈顶元素 } |
示例二&＃xff1a;遍历二叉树
二叉树的先序遍历&＃xff0c;中序遍历&＃xff0c;后序遍历&＃xff0c;通常是递归实现的&＃xff0c;因为很好理解。此处不再赘述递归版本。
假设有一个二叉树&＃xff1a;
先用代码构造出这棵树。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #region 节点的定义class node{ public string nodevalue; public node leftchild, rightchild; public node() { } public node(string value) { nodevalue &＃61; value; } public void assignchild(node left, node right)//设定左右孩子 { this.leftchild &＃61; left; this.rightchild &＃61; right; } public bool hasleftchild//是否有左孩子 { get { return (leftchild !&＃61; null); } } public bool hasrightchild//是否有右孩子 { get { return (rightchild !&＃61; null); } } public override string ToString() { return nodevalue; }}#endregion |
***************************
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | static void Main(string[] args) { node node_a &＃61; new node("a"); node node_b &＃61; new node("b"); node node_c &＃61; new node("c"); node node_d &＃61; new node("d"); node node_e &＃61; new node("e"); node node_f &＃61; new node("f"); node node_g &＃61; new node("g"); node node_h &＃61; new node("h"); node node_i &＃61; 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); } |
****************************************
非递归版本实现先序遍历。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | //先序遍历 static void preorder_visit_1(node root) { Stacknew Stack s.Push(root);//先序遍历。首先访问的是根结点&＃xff0c;把根节点放入栈中 while (s.Count > 0) { node r &＃61; s.Pop();//当前要访问的结点出栈。 Console.Write(r.nodevalue); //先序遍历的顺序是根&＃xff0c;左&＃xff0c;右。 //由于栈的先入后出的特性&＃xff0c;因此先插入右孩子&＃xff0c;后插入左孩子&＃xff0c;能保证取出来的时候是先左后右 if (r.hasrightchild) //如果有右孩子&＃xff0c;则右孩子入栈 { s.Push(r.rightchild); } if (r.hasleftchild)//如果有左孩子&＃xff0c;则左孩子入栈 { s.Push(r.leftchild); } } }//中序遍历 static void inorder_visit_1(node root) { Stacknew Stack s.Push(root); while (s.Count > 0) { while (s.Peek() !&＃61; null && s.Peek().hasleftchild)//把该节点的左子树全部遍历。 //如果s.Peek()&＃61;&＃61;null,说明栈中null下的元素的左孩子已经遍历过了&＃xff0c;该访问null下的元素本身了。 { s.Push(s.Peek().leftchild); } if (s.Peek() &＃61;&＃61; null) s.Pop(); if (s.Count > 0) { var node &＃61; s.Pop(); Console.Write(node.nodevalue); s.Push(node.rightchild);//如果没有右子树&＃xff0c;放入空结点 } } } |
京公网安备 11010802041100号