Theoretical analysis of a recursive function

1

Hello there!

Could someone please help me to wrap my head around this function’s calls and how does it achieve the desired result?

It´s pretty simple, but I am still confused.

const reverseString = (str) => str === "" ? "" : reverseString(str.substr(1)) + str.charAt(0);

reverseString("abc"); //call the function

//1st Call:    bc + a  => reverseString(bc)

///2nd Call: c  + b  => reverseString(c)

///3rd Call:  "" + c  => reverseString("")

// 4th Call: END

This bewilders my mind… reverseString("abc") returns cba, but I do not understand how is this possible.

Thinking over the process, I do understand that the more nested functions are called before, leading to this reversion of the string, but what I don´t figure is how come the result is the one presented, as the calls are composed by str.substr(1) + str.charAt(0).

Analyzing the result and looking at the calls, it seems like the result of this function is brought by str.charAt(0) itself alone.

I appreciate in advance for whoever spares some minutes here with me.

Cheers

2

reverseString is called again with the string without the first character, and then to the result is concatenated the first character if the array

so you have practically reverseString("bc") + "a"
and this continue
inside this function call you have reverseString("c") + "b"
and inside this one is reverseString("") + "c"

making it as a whole "" + "c" + "b" + "a"

3

@ILM thanks for dedicating some of your time to help me out.

is called again with the string without the first character, and then to the result is concatenated the first character if the array

You mean that every time reverseString(str) is called, whatever is being passed to str.charAt(0) is concatenated to an array, while str.substr(1), passed in each call, keeps overwriting itself, resulting in an empty string at its last call?

In other words, the values passed inside the argument in the recursive call is replaced at every time the recursion occurs, while str.charAt(0)remains concatenating ending at the desired result?

What I do not understand is how come the data passed by str.charAt(0) is concatenated into an array. I could only imagine these values being kept somehow through the recursive calls by seeing a variable storing str.charAt(0) at every call, e.g array.push(str.charAt(0)) at every call. Starring at str.charAt(0) here makes me imagine that this value is also being overwritten.

I guess that the result of the function, at every call should be a string, so each value passed to str.charAt(0) will keep being added at each call: c + b + a.

Sorry for the long text… I really want to understand these interesting details.

Once more, thanks for sparing some of your precious time =D

Cheers

4

I think it always helps to write the function out in an expanded form when it’s unclear

function reverseString(str) {
  console.log("Called With: " + str);

  if (str === "") {
    // Base Case
    console.log(" - Base Case");

    const result = "";
    console.log("   Result: " + result);

    return result ;
  } else {
    // Recursive Case
    console.log(" - Recursive Case");

    const currentChar = str.charAt(0);
    console.log("   Current: " + currentChar);

    console.log("   Making Recursive Call!");
    const restOfString = reverseString(str.substr(1));

    const result = restOfString + currentChar;
    console.log("   Result: " + result);

    return result;
 }
}

Try running this version (may require minor debuging; I wrote it on my phone)

1 Like