本篇內(nèi)容介紹了“如何用java遞歸實現(xiàn)1到100的相加”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)建站成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目做網(wǎng)站、成都做網(wǎng)站網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元冊亨做網(wǎng)站,已為上家服務(wù),為冊亨各地企業(yè)和個人服務(wù),聯(lián)系電話:13518219792

何為遞歸？

所謂遞歸，是指程序在運行的過程中調(diào)用自身的行為。

這種行為也不能無限制地進行下去，得有個出口，叫做邊界條件，所以，遞歸可以分成三個段：前進段、達到邊界條件，返回段，在這三個段我們都可以做一些事，比如前進段對問題規(guī)模進行縮小，返回段對結(jié)果進行整理。

這么說可能比較抽象，讓我們看一個簡單的案例：

如何用遞歸實現(xiàn)1到100的相加？

1到100相加使用循環(huán)大家都會解，代碼如下：

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;
    }
}

那么，如何使用遞歸實現(xiàn)呢？

如何快速實現(xiàn)遞歸？

首先，我們要找到這道題的邊界條件，1到100相加，邊界條件可以是1，也可以是100，如果從1開始，那么邊界條件就是100，反之亦然。

找到了邊界條件之后，就是將問題規(guī)模縮小，對于這道題，計算1到100相加，那么，能不能先計算1到99相加再把100加上呢？肯定是可以的，這樣問題的規(guī)模就縮小了，直到，問題規(guī)?？s小為1到1相加為止。

OK，讓我們看代碼實現(xiàn)：

private static int sumRecursive(int min, int max) {
    // 邊界條件
    if (min >= max) {
        return min;
    }
    // 問題規(guī)?？s小
    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?

所以，使用遞歸最重要的就是找到邊界條件，然后讓問題的規(guī)模朝著邊界條件的方向一直縮小，直到達到邊界條件，最后依次返回即可，這也是快速實現(xiàn)遞歸的套路。

這么看來，使用遞歸似乎很簡單，但是，它有沒有什么缺點呢？

要了解缺點就得從遞歸的本質(zhì)入手。

遞歸的本質(zhì)是什么？

我們知道，JVM啟動的時候有個參數(shù)叫做-Xss，它不是表示XSS攻擊哈，它是指每個線程可以使用的線程棧的大小。

那么，什么又是線程棧呢？

棧大家都理解了，我們在前面的章節(jié)也學習過了，使用棧，可以實現(xiàn)計算器的功能，非常方便。

線程棧，顧名思義，就是指線程運行過程中使用的棧。

那么，線程在運行的過程中為什么要使用棧呢？

這就不得不說方法調(diào)用的本質(zhì)了。

舉個簡單的例子：

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() 調(diào)用 方法b()，方法b() 調(diào)用 方法c()，在實際運行的過程中，是這樣處理的：調(diào)用方法a()時，發(fā)現(xiàn)需要調(diào)用方法b()才能返回，那就把方法a()及其狀態(tài)保存到棧中，然后調(diào)用方法b()，同樣地，調(diào)用方法b()時，發(fā)現(xiàn)需要先調(diào)用方法c()才能返回，那就把方法b()及其狀態(tài)入棧，然后調(diào)用方法c()，調(diào)用方法c()時，不需要額外調(diào)用別的方法了，計算完畢返回，返回之后，從棧頂取出方法b()及當時的狀態(tài)，繼續(xù)運行方法b()，方法b()運行完畢，返回，再從棧中取出方法a()及當時的狀態(tài)，計算完畢，方法a()返回，程序等待結(jié)束。

還是上圖吧：

所以，方法調(diào)用的本質(zhì)，就是棧的使用。

同理，遞歸的調(diào)用就是方法的調(diào)用，所以，遞歸的調(diào)用，也是棧的使用，不過，這個棧會變得非常大，比如，對于1到100相加，就有99次入棧出棧的操作。

因此，總結(jié)起來，遞歸有以下兩個缺點：

1. 操作耗時，因為牽涉到大量的入棧出棧操作；

2. 有可能導(dǎo)致線程棧溢出，因為遞歸調(diào)用占用了線程棧很大的空間。

那么，我們是不是就不要使用遞歸了呢？

當然不是，之所以使用遞歸，就是因為它使用起來非常簡單，能夠快速地解決我們的問題，合理控制遞歸調(diào)用鏈的長度，就是一個好遞歸。

既然，遞歸調(diào)用的本質(zhì)，就是棧的使用，那么，我們能不能自己模擬一個棧，將遞歸調(diào)用改成非遞歸呢？

當然可以。

修改遞歸為非遞歸的套路

還是使用上面的例子，現(xiàn)在我們需要把遞歸修改成非遞歸，且不是使用for循環(huán)的那種形式，要怎么實現(xiàn)呢？

首先，我們要自己模擬一個棧；

然后，找到邊界條件；

最后，朝著邊界條件的方向縮小問題規(guī)模；

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 {
                // 問題規(guī)?？s小到一定程度，計算返回
                sum += stack.pop();
            }
        }
        return sum;
    }

好了，是不是很簡單，其實跟遞歸的套路是一樣的，只不過改成自己模擬棧來實現(xiàn)。

這個例子可能不是那么明顯，我們再舉個二叉樹遍歷的例子來看一下。

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);
    }
}

我這里隨手寫了一顆二叉樹，并實現(xiàn)了其先序遍歷，這個測試用例中的二叉樹長這個樣子：

所以，這個二叉樹的先序遍歷結(jié)果為3,1,0,2,7,5,4,6,8,9,。

可以看到，使用遞歸先序遍歷二叉樹非常簡單，而且代碼清晰易懂，那么，它如何修改為非遞歸實現(xiàn)呢？

首先，我們要自己模擬一個棧；

然后，找到邊界條件，為節(jié)點等于空時；

最后，縮小問題規(guī)模，這里是先把右子樹壓棧，再把左子樹壓棧，因為先左后右；

好了，來看代碼實現(xiàn)：

// 先序遍歷非遞歸形式
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 + ",");
            // 縮小問題規(guī)模
            stack.push(tmp.right);
            stack.push(tmp.left);
        }
    }
}

“如何用java遞歸實現(xiàn)1到100的相加”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

當前文章：如何用java遞歸實現(xiàn)1到100的相加
文章URL：http://chinadenli.net/article16/pijcgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站收錄、網(wǎng)站排名、網(wǎng)頁設(shè)計公司、網(wǎng)站內(nèi)鏈、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)