java - 需要帮助来了解这种双重递归

我有一些代码

public class NameGenerator {
public static void main (String[] args)
{
    List<String> result = new ArrayList<String>();
    buildNameChoices("von.del.smith", result);
    System.out.println(result);
}
public static void buildNameChoicesHelper(String[] nameArray, int nameIndex,
    String firstName, String lastName, List<String> result) {

    if(nameIndex >= nameArray.length) {
        if(lastName.length() > 0) {
            result.add(firstName + lastName);
        }
    }
    else {
        System.out.println("Calling first buildNameChoices");
        buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result);
        System.out.println("Calling second buildNameChoices");
        buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName + "." + nameArray[nameIndex], result);
    }
}
public static void buildNameChoices(String nameStr, List<String> result) {
    String[] nameArray = nameStr.split("\\.", -1);
    for(int i = 0; i < nameArray.length; i++) {
        System.out.println("Inside for loop");
        buildNameChoicesHelper(nameArray, i + 1, nameArray[i], "", result);
    }
}

}

生成所传递的名称字符串的所有可能组合。该代码有效，并且我了解了递归在某种程度上是如何工作的，但是双重递归调用确实使我感到困惑。我已经看了很长时间了，但是我很难确切地了解它在做什么。任何帮助，将不胜感激。我已经尝试通过它进行调试，但是我仍然无法真正理解它。

最佳答案

您可以将递归想象为执行堆栈。


buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result);被调用并添加到堆栈的顶部
如果if(nameIndex >= nameArray.length)是匹配的，我们将检查堆栈中是否还有元素，如果是，则向下进行一步，然后执行步骤3，否则就完成了。如果条件不匹配，则执行步骤1
我们从buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result);的调用返回，因此继续调用添加在堆栈顶部的buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName + "." + nameArray[nameIndex], result);，从1开始


您的示例的调用栈如下所示：

//execution 1
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "2", firstName: "von", lastName: "", result: "[]");

stack = [execution1];

//execution 2
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "von", lastName: "", result: "[]");

stack = [execution1, execution2];

// nameIndex >= nameArray.length -> step 2 -> step3
stack = [execution1];

// execution 3
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "von", lastName + "." + nameArray[nameIndex]: ".smith", result: "[]");

stack = [execution1, execution3];

// nameIndex >= nameArray.length -> step 2 -> step3
stack = [execution1];

//execution 4
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "2", firstName: "von", lastName + "." + nameArray[nameIndex]: ".del", result: "[von.smith]");

stack = [execution1,execution4];


// exectution 5
// we are back at step 1
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "von", lastName: ".del", result: "[von.smith]");

stack = [execution1,execution4,execution5];

// nameIndex >= nameArray.length -> step 2 -> step3
stack = [execution1,execution4];

// execution 6
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "von", lastName + "." + nameArray[nameIndex]: ".del.smith", result: "[von.smith, von.del]");

stack = [execution1,execution4,execution6];

// nameIndex >= nameArray.length -> step 2 -> step3
stack = [execution1,execution4];

// execution 7
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "del", lastName: "", result: "[von.smith, von.del, von.del.smith]");

stack = [execution1,execution4,execution7];

// nameIndex >= nameArray.length -> step 2 -> step3
stack = [execution1];

// execution 8
buildNameChoicesHelper(nameArray: [von, del, smith],nameIndex: "3", firstName: "del", lastName + "." + nameArray[nameIndex]: ".smith", result: "[von.smith, von.del, von.del.smith]");

stack = [execution1, execution8];

//1 and 8 both terminate