用一種方法進行雙遞歸Java

我非常肯定，我完全理解只有一個遞歸的方法是如何工作的。用一種方法進行雙遞歸Java

例）計算階乘

public int factorial(int n){ //factorial recursion 
    if(n==0){ 
     return 1; 
    } 
    else{ 
     return n*factorial(n-1); 
    } 
}

對於這些方法，我甚至能想象這是怎麼回事了堆棧中，並在每個堆棧層正在返回什麼值。

但是每當我遇到雙遞歸的方法時，夢魘就開始了。

下面是一個遞歸問題，從編碼蝙蝠雙遞歸。鑑於整數數組

實施例），是有可能選擇一個組的一些整數的，使得該組總和爲給定的目標？如果是，則爲真。如果否，則爲false。您使用3個參數;起始索引開始，int數組NUMS，目標int值目標。

下面是解決這個問題的方法。

public boolean groupSum(int start, int[] nums, int target) { 
    if (start >= nums.length) return (target == 0); 
    if (groupSum(start + 1, nums, target - nums[start])) return true; 
    if (groupSum(start + 1, nums, target)) return true; 
    return false; 
}

我想了解這個解決方案是這樣的。假設我給了一個數組{2,4,8}，起始索引= 0，目標值爲10.因此，（0，{2,4,8}，10）通過該方法進入，函數獲取在

if (groupSum(start + 1, nums, target - nums[start])) return true;

-called所以它成爲(1,{2,4,8},8)直到開始索引命中
它一遍又一遍。當它打到3時。最後一級（？）的棧進入第二次遞歸調用。這就是我開始失去正在發生的事情的地方。

誰能打破這對我？當人們使用雙遞歸（我知道這是非常低效的，並且在實踐中，幾乎沒有人使用它來降低效率，但僅僅是試圖理解它），他們是否真的可以想象會發生什麼？還是他們只是用它希望基本情況和遞歸能正常工作？我想，這一般適用於誰寫的歸併排序，河內alogrithm等塔的所有脂肪酶..

任何幫助是極大的讚賞..

來源

2016-03-03 Hello

你在這裏發明術語。它不是沒有「雙遞歸」 - 你已經顯示的是一個普通的遞歸。而且，就像一個有智慧的人曾經說過的，「爲了理解遞歸，你必須首先理解遞歸」。 – vaxquis

以及我想我還沒有理解遞歸。所以請賜教。 – Hello

成爲我的客人：http：// stackoverflow。com/questions/3021/what-is-recursion-and-when-should-i-use-it https://en.wikipedia.org/wiki/Recursion http://stackoverflow.com/questions/126756/examples-遞歸函數 – vaxquis

雙遞歸的想法是把問題分解成兩個較小的問題。一旦你解決了小問題，你可以加入他們的解決方案（就像合併排序一樣）或者選擇其中的一個 - 在你的例子中完成，只需要解決第二個小問題就可以解決第一個小問題沒有解決完整的問題。

您的示例嘗試確定是否有輸入nums數組的其子集合的總和爲target總和。start確定當前遞歸調用考慮數組的哪一部分（當它是0時，整個數組被考慮）。

該問題被分解爲兩個，因爲如果存在這樣一個子集，它或者包含數組的第一個元素（在這種情況下，問題被簡化爲查找是否存在最後n-1個元素的子集的數組，其總和爲target減去第一個元素的值）或不包含它（在這種情況下，問題被簡化爲查找是否存在數組的最後n-1個元素的子集，其總和爲target）。

第一個遞歸處理子集包含第一個元素的情況，這就是爲什麼它會進行遞歸調用，以查找目標總和減去數組剩餘n-1個元素中的第一個元素。如果第一次遞歸返回true，則意味着需要的子集存在，所以第二次遞歸永遠不會被調用。

第二次遞歸處理子集不包含第一個元素的情況，這就是爲什麼它會進行遞歸調用，以便在數組的剩餘n-1個元素中查找目標總和（此時爲第一個元素不會從目標總和中減去，因爲第一個元素不包含在總和中）。同樣，如果第二次遞歸調用返回true，則意味着需要的子集存在。

來源

2016-03-03 12:29:00 Eran

我認爲函數可以有1個改進 - 它可以在第一行檢查'target == 0'，並且在我們已經到達目標後立即檢查'返回true' - 目前它不必要地遍歷整個數組。你怎麼看？ – radoh

謝謝你的回覆。但是，你能解釋爲什麼它被分爲兩個有或沒有第一個元素？爲什麼不考慮其他因素？ – Hello

@LookAtTheBigPicture有很多方法可以將問題分解爲更小的部分。您可以考慮前兩個元素，然後將問題分解爲四個部分（根據前兩個元素中是否都有任何一個出現在具有目標總和的子集中）。不過，這會使代碼更復雜。 – Eran

嘗試去了解它是這樣的：遞歸可改寫爲一段時間-循環。其中時間的條件是否定遞歸的停止條件。

前面已經說過，沒有什麼所謂的雙遞歸。

來源

2016-03-03 12:28:06 adranale

那麼，如果你想要可視化它，通常它就像一棵樹。您首先沿着樹中的一條路徑走到最後，然後再回到另一條路徑並選擇不同的路徑（如果可能的話）。如果沒有或者你對結果滿意，你只需要再退一步等等。

我不知道這是否對你有幫助，但是當我學習遞歸時，它幫助我想到我的方法已經在工作。所以我想：很好，所以基本上我的方法已經工作，但我不能用相同的參數調用它，並且必須確保通過使用不同的參數來返回這些確切參數的正確值。

如果我們採取的例子：首先，我們知道，如果我們沒有數字來看看左邊，那麼答案取決於目標是否爲0（第一行）

現在我們該怎麼辦剩下的？那麼......我們需要考慮一下。只要想想第一個數字。在什麼情況下它是解決方案的一部分？那麼，如果你可以用剩下的數字創建目標優先數。因爲那麼當你添加firstnumber時，你達到目標。所以你試圖看看這是可能的。如果是這樣，它是可以解決的。（第二行）

但是，如果不是，仍然有可能第一個數字對解決方案不重要。所以你必須再次嘗試構建沒有這個數字的目標。（第三行）

而這基本上都是這樣的。

當然要這樣想，你需要兩件事： 1.你需要相信你的方法已經適用於其他參數 2.你需要確保遞歸終止。這是本示例中的第一行，但您應該始終考慮是否有任何參數組合會創建無限遞歸。

來源

2016-03-03 13:56:33

用一種方法進行雙遞歸Java

回答

相關問題