本文共 2171 字，大约阅读时间需要 7 分钟。

【直接转化 】

消除尾递归和单向递归 1. 尾递归 指在递归算法中递归调用语句只有一个 且处于算法的最后

private static int factorialByRecurision(int num) {   if (num == 1) {        return 1;    }    return num * factorialByRecurision(num - 1);}

想上面的阶乘改成循环实现:

private static int factorialByLoop(int num) {   int result = 1;    for (int i = 2; i <= num; i++) {        result *= i;    }    return result;}

对于尾递归形式的递归算法 转换成循环时无需用stack保存中间结果

2.单向递归

多处递归调用 但是递归之间没有直接的关系 并且这些递归都处于算法的最后

private static int fibonacciByRecursion(int num) {   if (num == 1 || num == 2) {        return 1;    }    return fibonacciByRecursion(num - 1) + fibonacciByRecursion(num - 2);}

转成循环实现Fibonacci数列

private static int fibonacciByLoop(int num) {    if (num == 1 || num == 2) {        return 1;    }    int s1 = 1, s2 = 1;    int result = 0;    for (int i = 3; i <= num; i++) {        result = s1 + s2;        s1 = s2;        s2 = result;    }    return result;}

【间接转换法】

使用栈保存中间结果 应用场景: 二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现 使用方法一般是:

初始状态s0入栈whle(栈不为空){    退栈 栈顶元素赋给s    if(s是要找的元素)         返回s;    else{        找到s的相关状态s1        s1入栈    }}

二叉树遍历的例子

用递归实现先序遍历

public static void traversalTreeByRecursion(BinaryTreeNode root) {  if (root == null) {        return;    }    System.out.print(root.value + " ");    traversalTreeByRecursion(root.leftNode);    traversalTreeByRecursion(root.rightNode);}

使用循环实现先序遍历

1.用栈

public static void traversalTreeByLoop(BinaryTreeNode root) {    Stack
   
     stack = new Stack<>();    stack.push(root);    while (!stack.empty()) {        BinaryTreeNode temp = stack.pop();        System.out.print(temp.value + " ");        if (temp.rightNode != null) {            stack.push(temp.rightNode);        }        if (temp.leftNode != null) {            stack.push(temp.leftNode);        }    }}
   

2.用队列

public static void traversalTreeByLoop2(BinaryTreeNode root) {   Queue
   
     queue = new LinkedBlockingQueue<>();    queue.add(root);    while (!queue.isEmpty()) {        BinaryTreeNode temp = queue.poll();        System.out.print(temp.value + " ");        if (temp.leftNode != null) {            queue.add(temp.leftNode);        }        if (temp.rightNode != null) {            queue.add(temp.rightNode);        }    }}
   

---

转载地址：http://thqli.baihongyu.com/