確定遞歸Java程序的基本情況

Question

此代碼生成一組數字的powerset。例如，如果我們有（0,1,2）冪集是{（0,1,2），（0,2），（1,2），（0,1），（2），（1） ，（0），（）}

public static List<List<Integer>> generatePowerSet(List<Integer> inputSet){ 
    List<List<Integer>> powerSet = new ArrayList<>(); 
    directedPowerSet(inputSet,0,new ArrayList<Integer>(), powerSet); 
    return powerSet; 
} 
public static void directedPowerSet(List<Integer> inputSet, int toBeSelected, List<Integer> selectedSoFar,List<List<Integer>> powerSet){ 
    if(toBeSelected == inputSet.size()){ 
     powerSet.add(new ArrayList<Integer>(selectedSoFar)); 
     return; 
    } 
    //Generate all subsets that contain inputSet[toBeSelected]. 
    selectedSoFar.add(inputSet.get(toBeSelected)); 
    directedPowerSet(inputSet,toBeSelected+1,selectedSoFar,powerSet); 
    //Generate all subsets that do not contain inputSet[toBeSelected]. 
    selectedSoFar.remove(selectedSoFar.size()-1); 
    directedPowerSet(inputSet,toBeSelected+1,selectedSoFar,powerSet); 
} 

爲什麼在基本情況下toBeSelected == inputSet.size（）？

Answer 1

遞歸代碼從0開始一個接一個地進入inputSet列表中。當前調用使用toBeSelected作爲inputSet的索引，並將toBeSelected+1傳遞給下一級別的調用。

因此，基本情況的含義是沒有別的選擇，當toBeSelected變得無效時發生。

toBeSelected的最後一個有效值是inputSet.size()-1; toBeSelected==inputSet.size()檢測到第一個無效值toBeSelected，作爲遞歸的基本情況。

Answer 2

因爲代碼試圖建立一個元素集的功率集，從0元素空集開始，然後移動到1個元素集，然後移動到2個元素集，依此類推。

什麼時候該結束？當你最終嘗試構建一個元素集時，因爲只有一個元素集，這就是輸入集本身。