关于java:最新情报所有的递归都可以改写成非递归

本文收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节，咱们应用位图介绍了 12306 抢票算法的实现，没有收到推送的同学能够点击上方专辑查看，或者在公主号历史音讯中查看。

在上一节的最初，彤哥收到最新情报，说是所有的递归都能够改写成非递归，是不是真的呢？如何实现呢？有没有套路呢？

让咱们带着这些问题进入明天的学习吧。

所谓递归，是指程序在运行的过程中调用本身的行为。

这种行为也不能无限度地进行上来，得有个进口，叫做 边界条件，所以，递归能够分成三个段：后退段、达到边界条件，返回段，在这三个段咱们都能够做一些事，比方后退段对问题规模进行放大，返回段对后果进行整顿。

这么说可能比拟形象，让咱们看一个简略的案例：

如何用递归实现 1 到 100 的相加？

1 到 100 相加应用循环大家都会解，代码如下：

public class Sum {public static void main(String[] args) {System.out.println(sumCircle(1, 100));
    }

    private static int sumCircle(int min, int max) {
        int sum = 0;
        for (int i = min; i <= max; i++) {sum += i;}
        return sum;
    }
}

那么，如何应用递归实现呢？

首先，咱们要找到这道题的边界条件，1 到 100 相加，边界条件能够是 1，也能够是 100，如果从 1 开始，那么边界条件就是 100，反之亦然。

找到了边界条件之后，就是将问题规模放大，对于这道题，计算 1 到 100 相加，那么，能不能先计算 1 到 99 相加再把 100 加上呢？必定是能够的，这样问题的规模就放大了，直到，问题规模放大为 1 到 1 相加为止。

OK，让咱们看代码实现：

private static int sumRecursive(int min, int max) {
    // 边界条件
    if (min >= max) {return min;}
    // 问题规模放大
    int sum = sumRecursive(min, max - 1);
    // 加上以后值
    sum += max;
    // 返回
    return sum;
}

是不是很简略？还能够更简略：

private static int sumRecursive2(int min, int max) {return min >= max ? min : sumRecursive2(min, max - 1) + max;
}

686?

所以，应用递归最重要的就是找到边界条件，而后让问题的规模朝着边界条件的方向始终放大，直到达到边界条件，最初顺次返回即可，这也是疾速实现递归的套路。

这么看来，应用递归仿佛很简略，然而，它有没有什么毛病呢？

要理解毛病就得从递归的实质动手。

咱们晓得，JVM 启动的时候有个参数叫做-Xss，它不是示意 XSS 攻打哈，它是指每个线程能够应用的线程栈的大小。

那么，什么又是线程栈呢？

栈大家都了解了，咱们在后面的章节也学习过了，应用栈，能够实现计算器的性能，十分不便。

线程栈，顾名思义，就是指线程运行过程中应用的栈。

那么，线程在运行的过程中为什么要应用栈呢？

这就不得不说办法调用的实质了。

举个简略的例子：

private static int a(int num) {
    int a = 1;
    return a + b(num);
}

private static int b(int num) {
    int b = 2;
    return c(num) + b;
}

private static int c(int num) {
    int c = 3;
    return c + num;
}

在这段代码中，办法 a() 调用办法 b()，办法 b() 调用办法 c()，在理论运行的过程中，是这样解决的：调用办法 a()时，发现须要调用办法 b()能力返回，那就把办法 a()及其状态保留到栈中，而后调用办法 b()，同样地，调用办法 b()时，发现须要先调用办法 c()能力返回，那就把办法 b()及其状态入栈，而后调用办法 c()，调用办法 c()时，不须要额定调用别的办法了，计算结束返回，返回之后，从栈顶取出办法 b()及过后的状态，持续运行办法 b()，办法 b()运行结束，返回，再从栈中取出办法 a()及过后的状态，计算结束，办法 a()返回，程序期待完结。

还是上图吧：

所以，办法调用的实质，就是栈的应用。

同理，递归的调用就是办法的调用，所以，递归的调用，也是栈的应用，不过，这个栈会变得十分大，比方，对于 1 到 100 相加，就有 99 次入栈出栈的操作。

因而，总结起来，递归有以下两个毛病：

操作耗时，因为牵涉到大量的入栈出栈操作；
有可能导致线程栈溢出，因为递归调用占用了线程栈很大的空间。

那么，咱们是不是就不要应用递归了呢？

当然不是，之所以应用递归，就是因为它应用起来非常简单，可能疾速地解决咱们的问题，正当管制递归调用链的长度，就是一个好递归。

既然，递归调用的实质，就是栈的应用，那么，咱们能不能自己模仿一个栈，将递归调用改成非递归呢？

当然能够。

还是应用下面的例子，当初咱们须要把递归批改成非递归，且不是应用 for 循环的那种模式，要怎么实现呢？

首先，咱们要本人模仿一个栈；

而后，找到边界条件；

最初，朝着边界条件的方向放大问题规模；

OK，上代码：

private static int sumNonRecursive(int min, int max) {
        int sum = 0;
        // 申明一个栈
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(max);
        while (!stack.isEmpty()) {if (max > min) {
                // 要计算 max，先计算 max-1
                stack.push(--max);
            } else {
                // 问题规模放大到肯定水平，计算返回
                sum += stack.pop();}
        }
        return sum;
    }

好了，是不是很简略，其实跟递归的套路是一样的，只不过改成本人模仿栈来实现。

这个例子可能不是那么显著，咱们再举个二叉树遍历的例子来看一下。

public class BinaryTree {

    Node root;

    // 插入元素
    void put(int value) {if (root == null) {root = new Node(value);
        } else {
            Node parent = root;
            while (true) {if (value <= parent.value) {if (parent.left == null) {parent.left = new Node(value);
                        return;
                    } else {parent = parent.left;}
                } else {if (parent.right == null) {parent.right = new Node(value);
                        return;
                    } else {parent = parent.right;}
                }

            }
        }
    }

    // 先序遍历
    void preTraversal(Node x) {if (x == null) return;
        System.out.print(x.value + ",");
        preTraversal(x.left);
        preTraversal(x.right);
    }

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {this.value = value;}
    }

    public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();
        binaryTree.put(3);
        binaryTree.put(1);
        binaryTree.put(2);
        binaryTree.put(7);
        binaryTree.put(8);
        binaryTree.put(5);
        binaryTree.put(4);
        binaryTree.put(6);
        binaryTree.put(9);
        binaryTree.put(0);

        binaryTree.preTraversal(binaryTree.root);
    }
}

我这里顺手写了一颗二叉树，并实现了其先序遍历，这个测试用例中的二叉树长这个样子：

所以，这个二叉树的先序遍历后果为3,1,0,2,7,5,4,6,8,9,。

能够看到，应用递归先序遍历二叉树非常简单，而且代码清晰易懂，那么，它如何批改为非递归实现呢？

首先，咱们要本人模仿一个栈；

而后，找到边界条件，为节点等于空时；

最初，放大问题规模，这里是先把右子树压栈，再把左子树压栈，因为先左后右；

好了，来看代码实现：

// 先序遍历非递归模式
void nonRecursivePreTraversal(Node x) {
    // 本人模仿一个栈
    Stack<Node> stack = new Stack<Node>();
    stack.push(x);
    while (!stack.isEmpty()) {Node tmp = stack.pop();
        // 隐含的边界条件
        if (tmp != null) {System.out.print(tmp.value + ",");
            // 放大问题规模
            stack.push(tmp.right);
            stack.push(tmp.left);
        }
    }
}

把握了这个套路是不是把递归改写为非递归非常简单，不过，改写之后的代码显然没有递归那么清晰。

好了，递归改写为非递归的套路咱们就讲到这里，不晓得你 Get 到了没有呢？你也能够找个递归本人来改写试试看。

本节，咱们从递归的概念动手，学习了如何疾速实现递归，以及递归的实质，最初，学习了递归改写为非递归的套路。

实质上，这也是栈这种数据结构的惯例用法。

既然讲到了栈，不讲队列是不是有点过分？

所以，下一节，遍历各种源码的彤哥将介绍如何实现高性能的队列，想理解其中的套路吗？还不快点来关注我！

关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。

关于java:最新情报所有的递归都可以改写成非递归

前言

何为递归？

如何疾速实现递归？

递归的实质是什么？

批改递归为非递归的套路

后记