jordaniac89 jordaniac89 - 4 months ago 20
Java Question

Need help understanding this double recursion

I have some code

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);
}
}


}

that generates all possible combinations of a name string that it is passed. The code works, and I understand how the recursion works on some level, but the double recursive call is really confusing me. I've been looking at it for quite some time, and I'm having trouble grasping exactly what it's doing. Any help on this would be greatly appreciated. I've tried debugging through it, but I'm still not really able to understand it.

Answer

You can imagine the recursion as a Stack of Executions.

  1. buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result); is called and added ontop of the stack

  2. if if(nameIndex >= nameArray.length) is matched we look if there are still elements on the stack, if so we go one down and to step 3, else we are finished. if the condition is not matched the exectution proceeds in step 1

  3. we return from the call of buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result);and therefore proceed calling buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName + "." + nameArray[nameIndex], result); which is added ontop of the stack, start from 1

the callstack for your example looks like this:

//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
Comments