Why does this recursive function return undefined?

by

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.

More Related Contents:

  1. How to write recursive function javascript push my array property Json object?
  2. Javascript a recursive function with no clear base case?
  3. How can I convert this JavaScript recursive function to an iterative one? [closed]
  4. How do I replace while loops with a functional programming alternative without tail call optimization?
  5. Building a promise chain recursively in javascript – memory considerations
  6. How does this recursion work?
  7. Recursion in Angular directives
  8. Typescript recursive function composition
  9. Are functions in JavaScript tail-call optimized?
  10. Recursively print all permutations of a string (Javascript)
  11. javascript: recursive anonymous function?
  12. Check for repeated characters in a string Javascript
  13. What are the js recursion limits for Firefox, Chrome, Safari, IE, etc?
  14. JavaScript recursive search in JSON object
  15. Javascript recursive array flattening
  16. A clearer explanation for recursion and flow of execution in JavaScript?
  17. Run multiple recursive Promises and break when requested
  18. Recursively filter array of objects
  19. Javascript recursive function not returning value?
  20. ES6 Tail Recursion Optimisation Stack Overflow
  21. Generate permutations of JavaScript array [duplicate]
  22. Can I use additional parameters in recursion problems?
  23. recursive function vs setInterval vs setTimeout javascript
  24. Javascript recursion from Eloquent Javascript
  25. Jquery Ajax beforeSend and success,error & complete
  26. Recursive Promises Not Returning
  27. how to render child components in react.js recursively
  28. Will a recursive ‘setTimeout’ function call eventually kill the JS Engine?
  29. Recursive tree search in a nested object structure in JavaScript
  30. Renaming object keys recursively

Leave a Comment