递归转非递归的思路和例子

某些算法逻辑，用递归很好表述，程序也很好写。理论上所有的递归都是可以转换成非递归的。如果有些场合要求不得使用递归，那就只好改成非递归了。

通常改成非递归算法的思路，就是使用临时的一个栈来存放计算的临时值。

下面演示2个例子。

示例一：

假设有如下的递归函数

f(1)=3

f(2)=11

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

那么写成代码，这个递归函数就是如下：

1 2 3 4 5 6 7 8 9

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的值。具体代码如下：

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 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();//返回栈顶元素         }

示例二：遍历二叉树

二叉树的先序遍历，中序遍历，后序遍历，通常是递归实现的，因为很好理解。此处不再赘述递归版本。

假设有一个二叉树：

先用代码构造出这棵树。

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 = 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

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

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

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

非递归版本实现先序遍历。

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)         {             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);//如果没有右子树，放入空结点                 }             }         }