1. 直接转换法
直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。
尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：
long fact(int n)
{
if (n==0) return 1;
else return n*fact(n-1);
}
当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：
long fact(int n)
{
int s=0;
for (int i=1; i<=n;i++)
s=s*i; //用s保存中间结果
return s;
}
单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：
int f(int n)
{
if (n= =1 | | n= =0) return 1;
else return f(n-1)+f(n-2);
}
对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果，非递归函数如下：
int f(int n)
{
int i, s;
int s1=1, s2=1;
for (i=3; i<=n; ++i)
{
s=s1+s2;
s2=s1; // 保存f(n-2)的值
s1=s; //保存f(n-1)的值
}
return s;
}
2. 间接转换法
该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：
将初始状态s0进栈
while (栈不为空)
{
退栈，将栈顶元素赋给s;
if (s是要找的结果) 返回;
else
{
寻找到s的相关状态s1;
将s1进栈
}
}
间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等。
使用非递归方式实现递归问题的算法程序,不仅可以节省存储空间,而且可以极大地提高算法程序的执行效率【这个不是固定逻辑】
由于本人学习的是《严蔚敏数据结构》
找了网上的非递归逻辑
严蔚敏数据结构:
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data);
push(S,p->lchild);
} //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive
按照上面写了非递归的，结果死循环了，错误代码如下:
自己刚开始整的，用了栈，没发现自己递归调用了，^_^
/**
* 这都是自己编写^_^
* 多余出了栈
* @param node
*/
public void traversePreOrderByStack(Node<E> node) {
Stack<Node<E>> stack=new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
Node<E>temp=stack.pop();//这里一压一如没啥，但也没有bug
System.out.println(temp.value);
if (temp.left!=null) {
Node<E> left=temp.left;
traversePreOrderByStack(left);
}
if (temp.right!=null) {
Node<E> right=temp.right;
traversePreOrderByStack(right);
}
}
}
/**
* 根据常规的栈使用方式改造的
* @param node
*/
public void traversePreOrderByStack1(Node<E> node) {
Stack<Node<E>> stack=new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
Node<E>temp=stack.pop();
System.out.println(temp.value);
if (temp.left==null) {
return ;
}else {
traversePreOrderByStack1(temp.left);
if (temp.right==null) {//其实和上一个逻辑结构是一样的
return;
}else {
traversePreOrderByStack1(temp.right);
}
}
}
}
/** * 看了网上正确的，还是无法深的要领，结果死循环了 * @param node */ public void traverseInorderByStack1(Node<E> node) { Stack<Node<E>> stack = new Stack<>(); Node<E> p = node; stack.push(p); while (p != null || !stack.isEmpty()) { Node<E> qNode=p; p = stack.pop(); if (qNode!=p) { System.out.println(p.value); if (p.right != null) { stack.push(p.right); } if (p.left != null) { stack.push(p); p = p.left; } } } }
正确的方法一：
/**
* 在遍历左子节点前，保存右节点的信息
*
* @param node
*/
public void traverseInorderByStack2(Node<E> node) {
Stack<Node<E>> stack = new Stack<>();
Node<E> p = node;
stack.push(p);
while (!stack.isEmpty()) {
p = stack.pop();
System.out.println(p.value);
if (p.right != null) {
stack.push(p.right);
}
if (p.left != null) {
stack.push(p.left);//压进左子节点，然后通过这个栈的死循环出栈得到下个逻辑循环
}
}
}