Home > Net >  In recursion, why is this the output
In recursion, why is this the output

Time:12-11

just started learning javascript and I came across this code while learning recursion, could someone please break this down for me on why the output is [1,2,3,4,5]?

function rangeOfNumbers(startNum, endNum) {

  if (endNum - startNum === 0) {
    return [startNum];
  } else {
    var numbers = rangeOfNumbers(startNum, endNum - 1);
    numbers.push(endNum);
    return numbers;
  }
}
console.log(rangeOfNumbers(1,5))

I can't seem to grasp this line of code "var numbers = rangeOfNumbers(startNum, endNum - 1);"

All I know is that it calls itself again while subtracting 1 on endNum each call and pushes it into the numbers array

CodePudding user response:

I wrote some comments to the lines for you to graps the functional purpose of each, if you need a deeper understanding on what happens, try yousing the debug tool of your IDE (vscode for example).

There you will see you will step into the else statement, call the function recursively, jump again into the else and recursion until you hit the end defined in the first if, then you are done with calling recursion and everz recursive state will call the next line where you push the number and then return to the next higher recursion state.

So the runthrough with 1,3:

3 > 1, => recurse to 2>1, => recurse to 1=1, break recursion, push 1, step out, push 2, step out, push 3, then you are done

function rangeOfNumbers(startNum, endNum) {

  if (endNum - startNum === 0) { // This statement checks if the recursion has hit its end when endNum === startNum
    return [startNum]; // This is the point when the recursion is stopped
  } else {
    var numbers = rangeOfNumbers(startNum, endNum - 1); // If the recursion is not finished yet, the function will call itself with the reduced endNum
    numbers.push(endNum); // This is first called in the deepest recursion, so the first one to be added is 1, then it steps back to the recursion state one above and in this case adds the 2 to the array
    return numbers; // Finally we return to be done with the function
  }
}
console.log(rangeOfNumbers(1,5)) // This is the start, the function is called with the 2 parameters 1 and 5

CodePudding user response:

Let's assume (for now) that rangeOfNumbers(a,b) yields the list of numbers from a to b (inclusive).

Now the part that you specifically asked about makes sense: to get the list of numbers from startNum to endNum (inclusive):

  • Compute the list of numbers from startNum up to but not including endNum.
  • Add endNum to the end of that list

That leaves our pesky assumption: our function only works if it works for a shorter range. And this is where the if comes in: if the list only contains a single value, return a list of just that value, without making a recursive call (which should obviously be correct).

Which means:

  • The function works for lists of length 1 (the if code)
  • It works for lists of length 2 (by making a recursive call for a list of length 1, which we just established works).
  • It works for lists of length 3 (by making a recursive call for a list of length 2, which we just established works).
  • ...
  • It works for lists of length N (by making a recursive call for a list of length N-1, which we just established works).

Which means it works for any value of N that can represent a list's length.

CodePudding user response:

Adding logs will help you visualize what is going on in the code. It will show you how the calls are made and with what parameters. Note: Stackoverflow log does not have indenting so better to look at the browser's console to see it.

function rangeOfNumbers(startNum, endNum) {
  console.group("rangeOfNumbers called with ", startNum, endNum);
  console.log("Subtraction = ", endNum - startNum);
  if (endNum - startNum === 0) { // did we hit the end point?
    console.log("We got zero. Returning ", startNum);
    console.groupEnd();
    return [startNum];
  } else { // numbers are different
    console.log("Calling rangeOfNumbers inside of else");
    var numbers = rangeOfNumbers(startNum, endNum - 1); // Make a new call with end number reduced by one
    console.log("rangeOfNumbers call returned", numbers.join(", "));
    numbers.push(endNum);
    console.log("pushing ", endNum);
    console.log("numbers updated with", numbers.join(", "));
    console.groupEnd();
    return numbers;
  }
}
console.log(rangeOfNumbers(1,5))

  • Related