算法递归和循环的转换

骑猪看日落 2022-06-09 00:51 132阅读 0赞

【直接转化 】  
消除尾递归和单向递归  
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<BinaryTreeNode> 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<BinaryTreeNode> 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);
            }
        }
    }

--------------------