Why does this recursive function return undefined?

Question

I'm attempting to write a function that combines two strings using recursion. My code is below but I don't know why the function returns undefined especially when I console.log within the base case and it does not print undefined but instead the correct value.

var str3=""
function merge(str1,str2){
    if(str1.length==0||str2.length==0){
        console.log(str3)
        return str3;
    }
    else{
        str3=str3+str1.substring(0,1)+str2.substring(0,1);
        merge(str1.substring(1,str1.length),str2.substring(1,str2.length))
    }
}

merge("AAA","BBB") //--> returns undefined but the console.log(str3) gives correct answer

Answer 1

Explanation

The problem is that you don't return the recursive call's result, thus it is undefined when the whole call to merge is resolved.

Let me take you through the execution, step-by-step:

1. With arguments "AAA" and "BBB", their lengths are not 0, go to else. Once in else, str3 is "AB", call merge("AA", "BB").
2. With arguments "AA" and "BB", their lengths are not 0, go to else. Once in else, str3 is now "ABAB", call merge("A", "B").
3. With arguments "A" and "B", their lengths are not 0, go to else. Once in else, str3 is now "ABABAB", call merge("", "").
4. With empty string arguments, length is 0. Now go to the if statement, where str3 is logged, and returned.
5. Since the merge("", "") call has resolved (to "ABABAB" as it is returned), we continue where we left off in the call merge("A", "B"), thus going "up" the call stack.
6. We start where we left off in call merge("A", "B"), in the else branch. There are no more statements or expressions in that call, so it's resolved. There are no return statements, so by default it returns undefined. We go "up" the call stack to call merge("AA", "BB") where we left off.
7. We start where we left off in call merge("AA", "BB"), in the else branch. There are no more statements or expressions in that call, so it's resolved. Again, there are no return statements so by default it returns undefined. We go "up" the call stack to call merge("AAA", "BBB") where we left off.
8. We start where we left off in call merge("AAA", "BBB"), in the else branch. There are no more statements or expressions in that call, so it's resolved. Again, there are no return statements so by default it returns undefined. There are no more calls, so everything's resolved - and merge("AAA", "BBB") returns undefined.

TL;DR: The recursive call is not returned on each call in the else branch, so the value of str3 is returned to the call merge("A", "B"). The call merge("A", "B") does not return anything, it returns undefined. The same goes for all other calls - they have no return statement in the else branch so undefined is returned. When all calls are resolved, undefined is returned.

---

Solution

The solution is to simply prepend return to your recursive calls. That way, the result of each call would be returned, 'delegating' the final returned value of str3 up the call stack - the call returns "ABABAB", not undefined.

Since we now return the result of the call, steps 6, 7, and 8 above now have a return statement. That means we don't return undefined, but instead str3. This is because merge("", "") returned "ABABAB", which is the value of str3. That result is then returned in call merge("A", "B") because of the new added return statement, which is then returned in call merge("AA", "BB"), and so on, until the call is completely resolved, and the returns the value of str3.

Here's the new code:

var str3 = "";
function merge(str1, str2) {
    if(str1.length == 0 || str2.length == 0) {
        console.log(str3);
        return str3;
    } else {
        str3 = str3 + str1.substring(0, 1) + str2.substring(0, 1);
        return merge(str1.substring(1, str1.length), str2.substring(1, str2.length)); //we return the recursive call
    }
}

var mergedString = merge("AAA","BBB"); //mergedString is "ABABAB"

Before, mergedString would have received the value undefined. Since we now return the recursive calls, everything returned accordingly thus the value of str3 is returned, being stored into variable mergeString.