cannot understand logic of recursion

user_17830345 0
Viewed 44

This function has to return reversed string. For example, “dog” -> “god”. It works correctly but I don’t understand the logic and I need explanation

function reverse (str) {
   if (str.length <= 1) return str;
   return reverse(str.slice(1)) + str[0]
}
javascript
3 Answers

The base case of the recursive function is the if statement, where when there is just one character in the string, you get the string itself.

In the return statement, the slice function gives the string without the first character. The + str[0] helps reverse the string by attaching the first letter of the string to the end of the string, while the reverse function is recursively called on the string without the first character.

Let's look at the world TENET as an example.

In the first run, the if statement will not be called. The return statement will return reverse(ENET) + T. This will lead to reverse being called again with ENET as the input.

In the second run, the if statement is skipped again, and the return statement will give reverse(NET) + E.

Hopefully, you can see where this is going. In each recursive call, the first character is being added to the end of the input string. By the time we're through all the calls, the word will be reversed!

user_82496500

Explaination

Firstly, you call reverse(“dog”) and it return reverse(“og”)+”d” Then the reverse(“og”) continue to run again. It returns reverse(“g”)+”o” The last one, reverse(“g”) only returns “g” since the if statement is true

Then you plug the reverse(“g”) to the reverse(“g”)+”o”, as a result “go” is returned Finally, plug reverse(“og”) to reverse(“og”)+”d”, which is “go”+”d”, as a result “god” is the output

The flow

  • (1) reverse("dog") called -> return reverse("og")+"d"
  • (2) reverse("og") called -> return reverse("g")+"o"
  • (3) reverse("g") called -> return "g" (if statement)
  • (4) plug (3) to (2) -> return "g" + "o" -> "go"
  • (5) plug (4) to (1) -> return "go" + "d" -> "god"
user_156913990

There is no need for someone to write out the recursion behavior for one example, as one may not apply to all recursion types and orders.

It's best to run and debug the provided snippet, and watch the local stack trace and scoped values as you need to understand what it does on each call.

function reverse (str) {
   if (str.length <= 1) return str;
   debugger;
   const remainingString = str.slice(1);
   const leadingChar = str[0];
   return reverse(remainingString) + leadingChar;
}

In this example it is obligatory to understand only that this will execute first the reverse(remainingString) until we reach if (str.length <= 1) return str;, then pop functions from the call stack and add returned value with + leadingChar value until all functions are popped from the call stack.

user_109910820
Related