What are the order of operations in this recursive function?

user_446936 0
Viewed 238

Recursion in javascript is eluding me. I'm almost there, but I'm a bit confused about the order of operations. Take for example the following function:

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

Questions I'm trying to figure out:

  1. Does this create a closure around numbers?

  2. Does the function rangeOfNumbers return numbers every single time, or only once the recursion is completely finished?

  3. For the base case: Why are we returning an array with only startNum as the "base condition" ? Wouldn't this overwrite the numbers variable upon returning? I'm not sure how the base case works exactly. It seems to always return something that isn't what we are looking for, yet it controls when the function should stop executing (at the first start of the function call, and/or for ending it).

recursion javascript
3 Answers

Does this create a closure around numbers?

No, the numbers variable name is only referenceable while inside a single block (well, function), and it ends, nothing else has a reference to it. Nothing has saved a reference to it, so it's not a closure.

Does the function rangeOfNumbers return numbers every single time, or only once the recursion is completely finished?

In each recursive case, the numbers variable is returned. In the base case, a new array is returned. But since in recursive cases, the numbers variable is a reference to the array returned by the recursive call, the array returned up the chain each time is the same array.

For the base case: Why are we returning an array with only startNum as the "base condition" ? Wouldn't this overwrite the numbers variable upon returning?

In the base case, there is no numbers variable (unless you consider the hoisted variable name which never gets referenced). The array that gets returned becomes the numbers variable in the recursive calls, but in the base case itself, it's not the numbers variable.

Keep in mind that each call of a function results in separate bindings for its variables. For example, with

function fn(count) {
  const num = Math.random();
  return num + (count > 1 ? fn(count - 1) : 0);
}

Each call of fn has a separate num variable, which is a random number. The recursive call doesn't overwrite anything from prior calls.

For your rangeOfNumbers, the final recursive call results in the base case: the [startNum] array. This is returned to the recursive caller and gets stored into the numbers variable for that particular caller in

var numbers = rangeOfNumbers(startNum, endNum - 1);

Then, that one caller adds an item to the array and returns it to its caller, and the process repeats until the recursive call stack is completely unwound.

user_95152070

Consider this alteration to your function, the only difference being the logging:

function rangeOfNumbers(startNum, endNum) {
  if (endNum - startNum === 0) {
    console.log("Reached base case, returning: ");
    console.log([startNum]);
    return [startNum];
  } else {
    var numbers = rangeOfNumbers(startNum, endNum - 1);
    numbers.push(endNum);
    console.log("Returning " + numbers.join(','));
    return numbers;
  }
}

And then we call it like this:

rangeOfNumbers(0, 7);

And it will log

Reached base case, returning: 
VM60:4 [0]
VM60:9 Returning 0,1
VM60:9 Returning 0,1,2
VM60:9 Returning 0,1,2,3
VM60:9 Returning 0,1,2,3,4
VM60:9 Returning 0,1,2,3,4,5
VM60:9 Returning 0,1,2,3,4,5,6
VM60:9 Returning 0,1,2,3,4,5,6,7

So there's no closure. In the recursion, you dig all the way down to the base case, then add on to the array all the way back up.

user_37572320

Here's one way you can write your range function by increasing start -

const range = (start, end) =>
  start > end                             // terminating condition
    ? []                                  // base case
    : [ start, ...range(start + 1, end) ] // recursive step
    
console.log(range(5,10))
// [ 5, 6, 7, 8, 9, 10 ]

And another way we can write range by decreasing end -

const range = (start, end) =>
  end < start                             // terminating condition
    ? []                                  // base case
    : [ ...range(start, end - 1), end ]   // recursive step
    
console.log(range(5,10))
// [ 5, 6, 7, 8, 9, 10 ]

Notice the similarities and differences in each program

user_130763170
Related