瞭解遞歸如何與多個返回一起工作

Question

以下問題來自codingbat：給定一個int數組，是否可以選擇一組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; 
} 

---

假設我想嘗試以下情況下NUMS = [2,4,8]，並呼籲groupSum（0，NUMS ，10）。

我看到groupSum(0,nums,10)將叫groupSum(1,nums,10)和groupSum(1,nums,8)。

groupSum(1,nums,10)電話groupSum(2, nums,10)和groupSum(2, nums,6)

groupSum(1,nums,8)電話groupSum(2,nums,8)和groupSum(1,nums,4)

等等

通過我看到下面的調用的代碼工作：

groupSum(3,nums,10) 
groupSum(3,nums,2) 
groupSum(3,nums,6) 
groupSum(3,nums,-2) 
groupSum(3,nums,8) 
groupSum(3,nums,0) 
groupSum(3,nums,4) 
groupSum(3,nums,-4) 

我看到groupSum(3,nums,0)應該返回true，因爲第一行：
if (start >= nums.length) return (target == 0);但我很困惑其他電話，如groupSum(3,nums,-4)。從第一行開始，它應該明顯導致錯誤，因爲target != 0。

也有人解釋爲什麼迴歸真實的陳述是必要的，

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

我想的第一行會確定真假。

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

Answer 1

基本上功能可以被分解到這樣的：

1. 如果「開始」（當前號碼的數組中的位置）是部分陣列的端部（換句話說，如果我們已經嘗試了所有數字），那麼如果達到目標（即爲零），則函數成功（012）返回true

2. 否則，包括當前編號沒有工作，所以繼續迭代沒有當前編號。如果可以，返回true

3. 如果我們已經到了這一點，那麼就沒有辦法添加可用的數字，所以請返回false。

你已經分解了所有可能的函數調用的步驟，正如你觀察到的那樣，有一個返回true（目標爲零的那個）。這個true結果級聯備份遞歸作爲最終的返回值。

這裏是它如何工作的大概分類：

groupSum(0,[2,4,8],10) 
0 >= 3? no, so continue: 
groupSum(1,[2,4,8],10-2)? 
    1 >= 3? no, so continue: 
    groupSum(2,[2,4,8],8-4)? 
    2 >= 3? no, so continue: 
    groupSum(3,[2,4,8],4-8)? 
     3 >= 3? yes. -4 == 0? no, return false 
    groupSum(3,[2,4,8],4)? 
     3 >= 3? yes. 4 == 0? no, return false 
    return false 
    groupSum(2,[2,4,8],8)? 
    2 >= 3? no, so continue: 
    groupSum(3,[2,4,8],8-8)? 
     3 >= 3? yes. 0 == 0? yes, return true 
    yes, return true 
    yes, return true 
yes, return true 

希望這有助於！

Answer 2

除了Kolink的詳細穿行，什麼它的價值，在Java中，我創造了這個幫我看看：

public class TestRecursion{ 

    public static boolean groupSum(int start, int[] nums, int target, String s) { 
     System.out.println(new String(new char[start]).replace("\0", " ")+"start="+start+" target="+target+" parent="+s); 
     if (start >= nums.length) return (target == 0); 
     if (groupSum(start + 1, nums, target - nums[start], "A:"+start+"_"+target)) return true; 
     if (groupSum(start + 1, nums, target, "B:"+start+"_"+target)) return true; 
     return false; 
    } 

    public static void main(String... args){ 
     int[] nums = {2,4,8}; 
     groupSum(0, nums, 10, ""); 
    } 
} 

，輸出：

start=0 target=10 parent= 
    start=1 target=8 parent=A:0_10 
     start=2 target=4 parent=A:1_8 
      start=3 target=-4 parent=A:2_4 
      start=3 target=4 parent=B:2_4 
     start=2 target=8 parent=B:1_8 
      start=3 target=0 parent=A:2_8