前言

本文收录于专辑：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到了没有呢？你也能够找个递归本人来改写试试看。

后记

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

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

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

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

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