Need help understanding this double recursion

Question

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.

what exactly is it that you don't understand? The concept of a double recursion? Or why this particular case works? — Abaddon666, Jul 12 '16 at 21:33
Pretty much the whole concept. I don't really understand when the second one is called. Is it directly after the first one? Or is the first one called to the base case and then the second one called? — jordaniac89, Jul 12 '16 at 21:35
try and have a look at [this](http://stackoverflow.com/questions/19217565/understanding-double-recursion) it is a pretty explanation for a double recursion. — Abaddon666, Jul 12 '16 at 21:37
Thanks, I did look at that question, but I'm still struggling with the concept. Maybe if I keep looking at it, it will start clicking. — jordaniac89, Jul 12 '16 at 21:39
If you think about it in terms of stack frames (instances of the running method), whenever a recursive call is made another frame is placed on top of the stack. In the case of double recursion there is still only one stack at a time, but the stack will grow and shrink a number of times before the original method ends. This is because when the first recursive call is made in the original method, it must resolve that call BEFORE the second recursive call in the method can be executed. This is also the case with the recursive calls made in the method called by the original method. — J. Schei, Jul 12 '16 at 21:54

Abaddon666 · Accepted Answer · 2016-07-13T14:19:46.307

You can imagine the recursion as a Stack of Executions.

buildNameChoicesHelper(nameArray, nameIndex + 1,firstName, lastName, result); is called and added ontop of the stack
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
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

That actually helps a lot. I think it's easy to get confused when you have several stack frames waiting to be executed. — jordaniac89, Jul 13 '16 at 13:07
One quick question though. I see when the second recursive method is called in execution 3, the index is still 3 like it is in the first one. Why would that not be 4? — jordaniac89, Jul 13 '16 at 13:27
execution 3 is called by exectution1 and where the index is still 2, therefore it is 2+1=3 — Abaddon666, Jul 13 '16 at 13:38
I think I'm with you now. We are still on the first recursive call when the second recursive method is called. — jordaniac89, Jul 13 '16 at 13:42
yes exactly. The first recursion is called until the last call finishes, then the caller of this last one calls its second recursion which basically does the same. — Abaddon666, Jul 13 '16 at 13:50
Awesome. I think it's starting to come together for me. Thanks for the clear explanation! — jordaniac89, Jul 13 '16 at 14:04

Need help understanding this double recursion

1 Answers1