java - 如何使用递归来简化重复的代码？

Question

我有一个三角形/树？任何尺寸M。

在本例中，大小 M 为 3:

  1
 2 3
4 5 6     

我的目标是输出所有组合，就像从上到下遍历一样。结果将是{124}{125}{135}{136}

如何将 for 循环与递归结合起来以简化它

private ArrayList<int[]> listOfCombinations = new ArrayList<int[]>();
public void callSequence(int[] combo, int size, int n) {

    for (int i = 0; i < 4 && size >= 3; i++) {
        // System.out.println("combinations array :" + combo[0] + combo[1] + combo[2]);
        listOfCombinations.add(combo);
        listOfCombinations.get(i)[0] = 1;
        System.out.print(listOfCombinations.get(i)[0]);
    }
    System.out.println();
    for (int i=0; i < 2; i++) {
        listOfCombinations.add(combo);
        listOfCombinations.get(i)[1] = 2;
        System.out.print(listOfCombinations.get(i)[1]);
    }
    for (int i=2; i < 4; i++) {
        listOfCombinations.add(combo);
        listOfCombinations.get(i)[1] = 3;
        System.out.print(listOfCombinations.get(i)[1]);
    }
    System.out.println();
    for (int i=4; i<=5; i++) {
        listOfCombinations.get(i)[2] = i;
        System.out.print(listOfCombinations.get(i)[2]);
    }
    for (int i=5; i<=6; i++) {
        listOfCombinations.get(i)[2] = i;
        System.out.print(listOfCombinations.get(i)[2]);
    }

当我调用这个函数时，它会打印

 1 1 1 1
 2 2 3 3 
 4 5 5 6

所以数组是{1,2,4}{1,2,5}{1,3,5}{1,3,6}，这是正确的输出，但这是一个不好的方法。我正在尝试考虑如何用递归来做到这一点，这样我就可以简化它。

Answer 1

假设您的数据将如下所示:

RowNum:           Position:
  0                   1
  1                  2 3
  2                 4 5 6

然后你可以利用这样一个事实:左Position等于它上面的Position加上RowNum，右Position等于它上面的Position加上RowNum加1。所以，你可以构建一个递归算法像这样使用这个事实:

public static void main(String[] args) {
  int maxRows = 3;
  paths(maxRows, 1, 1, "1");
}

/**
 * Recursive top to bottom depth first approach
 * 
 * @param maxRow Total number of rows to travel down.
 * @param rowNum The current row an iteration is on.
 * @param position The position number above the current iteration.
 * @param values The values so far along the path.
 */
public static void paths(int maxRow, int rowNum, int position, String values) {
  //You've hit the bottom so print the results
  if(rowNum >= maxRow) {
    System.out.println(values);
    return;
  }

  int nextRow = rowNum + 1;

  //Calculate position for left side branch, append it to values, and start next iteration
  int leftPosition = position + rowNum;
  String leftValues = values + " " + leftPosition;
  paths(maxRow, nextRow, leftPosition, leftValues);

  //Calculate position for right side branch, append it to values, and start next iteration
  int rightPosition = position + rowNum + 1;
  String rightValues = values + " " + rightPosition;
  paths(maxRow, nextRow, rightPosition, rightValues);
}

编辑:这是一个将所有内容存储在容器中的版本，并有一个重载版本来简化用户实际需要的参数。

  public static void main(String[] args) {
    //Initializes the path function
    List<List<Integer>> allPaths = paths(4);
    System.out.println(allPaths);
  }

  /**
   * Recursively find all paths in a pyramid like node path. Depth first search.
   * <pre><code>
   * Row   Position     
   *  0        1       
   *  1       2 3     
   *  2      4 5 6    
   *  3     7 8 9 10 
   *  </code></pre>
   *  
   * @param maxDepth Total number of rows to travel down.
   * @return Collection of all the paths in their own collections.
   */
  public static List<List<Integer>> paths(int maxDepth) {
    List<List<Integer>> allPaths = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(1);
    paths(maxDepth, 1, 1, path, allPaths);
    return allPaths;
  }

  /**
   * Recursively find all paths in a pyramid like node path. Depth first search.
   *   
   * @param maxDepth Total number of rows to travel down.
   * @param currentDepth The current depth an iteration is on.
   * @param topPosition The position number above the current iteration.
   * @param currentPath The values so far along the path.
   * @param allPaths Container for all the paths when it reaches the end.
   */
  private static void paths(int maxDepth, int currentDepth, int topPosition, List<Integer> currentPath, List<List<Integer>> allPaths) {
    //You've hit the bottom so print the results
    if(currentDepth >= maxDepth) {
      allPaths.add(currentPath);
      return;
    }

    int nextDepth = currentDepth + 1;

    //Calculate position for left side branch, append it to values, and start it's branching iterations
    int leftPosition = topPosition + currentDepth;
    List<Integer> leftArray = new ArrayList<>(currentPath);
    leftArray.add(leftPosition);
    paths(maxDepth, nextDepth, leftPosition, leftArray, allPaths);

   //Calculate position for right side branch, append it to values, and start it's branching iterations
    int rightPosition = topPosition + currentDepth + 1;
    List<Integer> rightArray = new ArrayList<>(currentPath);
    rightArray.add(rightPosition);
    paths(maxDepth, nextDepth, rightPosition, rightArray, allPaths);
  }