某些算法逻辑，用递归很好表述，程序也很好写。理论上所有的递归都是可以转换成非递归的。如果有些场合要求不得使用递归，那就只好改成非递归了。
成都创新互联公司是一家专注于
成都网站设计、成都网站建设与策划设计,天桥网站建设哪家好?
成都创新互联公司做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:天桥等地区。天桥做网站价格咨询:18980820575
通常改成非递归算法的思路，就是使用临时的一个栈来存放计算的临时值。
下面演示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 s = new Stack();
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 s = new Stack();
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 s = new Stack();
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);//如果没有右子树，放入空结点
}
}
}另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：递归转非递归的思路和例子-创新互联
链接地址：
http://cdkjz.cn/article/dhjhhp.html
