Recursion challenge JS

This function returns and array of integers , starting from ’ startNum ’ and ending with ’ endNum '. I did create the base case accurately. However, I had to look up the later part.

Now what I do not understand is if we’re pushing (which adds the value at the end of the array) the ’ endNum ’ into the array, and the value is decrementing because of ’ - 1 ’ . How are the values incrementing in the array i.e. [1 , 2, 3, 4, 5] instead of going the other way.


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

Kindly tell me what am I missing here. I’m confused.

Thanks and regards.

We are creating an array while returning from the recursive calls. We reach the end of recursion and [1] comes back, then 2 is pushed to get [1, 2]. And so forth. Pictorially, we have

1 Like

This is really a great explanation. I understand it now. Thank you so much.

What I don’t get is that without understanding this call stack sequence (or whatever the actual term for that is), one cannot write any complicated recursive functions. So can you guide me where can I study this?

Because I feel if I understand how the stacking works, then recursion won’t be that hard for me.

There isn’t a lot that you need to understand about the call stack in order to be able to use it.

The key idea here is that every time you call a function, JavaScript has to wait until that function call starts, finishes, and returns before continuing to the next line in your code.

1 Like

I agree that you really don’t need to know about a call stack to be able write recursive routines. The only thing you need to be aware of is that each function call (recursive or otherwise) has its own copy of parameters and local variables.

I think the technique you want to master in order to write recursive functions naturally is how to decompose a problem into a solution that utilizes the same solution of a smaller set. For this problem, we decompose a solution [lo, lo+1, …, hi] in term of [lo, lo+1, …, hi-1] + [hi].

For a harder problem, this decomposition becomes harder, but the idea is the same. Suppose we want to generate all anagrams of a given word of length N, how can we decompose it? One way is to generate all anagrams of N-1 letters and insert the last letter into all positions. Here’s an example. Suppose the word is ‘CAT’. Possible anagrams for ‘CA’ are

CA
AC

Then you insert T into every possible position

T C A
C T A
C A T

T A C
A T C
A C T

So you make a recursive call to get all anagrams for N-1 letters and then add the last letter to all possible positions and return the answer. You stop the recursion when there’s only one letter left.

See how this recursion is “identical” to rangeOfNumbers?

2 Likes

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.