Explain this recursion function to me!

JavaScript
1

Tell us what’s happening:

I’m trying to understand how this function work.

I thought the IF statement would be executed last since that’s when endNum and startNum is the same.

However after logging the string within the IF statement, it appears it is the first thing executed.

In the ELSE statement you push the endNum and then return the function to go again with (endNum - 1).
In my head it pushes the 5 and then go again. That would mean the functions final result would be: 5 - 4 - 3 -2 -1.

BUT the result is the reverse: 1 - 2 - 3 - 4 - 5.

I understand that I can change the .push to .unshift - my problem isn’t the results, its me not understanding how the function work.

to formulate a question: Why is the IF statement executed in the beginning, and why does the ELSE statement count “up” when the code is to go (endNum -1)?

  **Your code so far**


function rangeOfNumbers(startNum, endNum) {
if (endNum - startNum === 0) {
  console.log(" this is 0")
  return [startNum];
} else {
  var numbers = rangeOfNumbers(startNum, endNum - 1);
  console.log(numbers + " before push")
  numbers.push(endNum);
  return numbers;
}
};

console.log(rangeOfNumbers(1, 5));



  **Your browser information:**

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/15.0 Safari/605.1.15

Challenge: Use Recursion to Create a Range of Numbers

Link to the challenge:

2

In a recursion, you have to think of the “stack” of function calls.
Every time the else-branch is entered, before the console.log() happens, the recursion is called again and then this instance is put on break, while the recursive call has to be sorted out. That’s why the following console.log() isn’t executed, the function is in a holding pattern.

Meaning the stack is build up, like a tower of papers. Every paper put on top of the last, because every new paper contains a calculation that has to be solved before the calculation on the previous paper can be continued.

So while the if-branch is the last one to be called (as there is no recursion inside), it reaches the console.log() - then returns the value. Meaning it’s result is taken, the top paper removed and the next paper can now work with it → it’s value is assigned to number THEN it’s reaching the console.log().

In short: the recursion builds a stack of unfinished functions first and then solves those from last to first. Hence the final call is the first one to be fully executed.

2 Likes
3

I’ve added some other prints to console to make following it a bit easier.

function rangeOfNumbers(startNum, endNum) {
  console.log(`rangeOfNumbers(${startNum}, ${endNum})`);
  if (endNum - startNum === 0) {
    console.log(" this is 0")
    return [startNum];
  } else {
    console.log(`calling rangeOfNumbers(${startNum}, ${endNum - 1})`);
    var numbers = rangeOfNumbers(startNum, endNum - 1);
    console.log(`rangeOfNumbers(${startNum}, ${endNum - 1}) returned`, numbers);
    
    numbers.push(endNum);
    return numbers;
  }
};
2 Likes
4

I am amazed at how fast and how brilliant these answers are.

This was my first question here - and didn’t really have that high expectation.

Thank you both for truly illuminating answers.

5

This helped me to fully understand it:
https://www.youtube.com/watch?v=LteNqj4DFD8

1 Like
6

Hi @Sparv1,

JS uses the abstractions:

  • nested (function) calls
  • call stack (data structure, LIFO: last in first out)

You can use python tutor to see step by step how the function is executed:

https://pythontutor.com/live.html#mode=edit

I wrote a short faq about recursion using the exercise, the code is different but I think it will help you to understand how the function work:

code

function rangeOfNumbers(startNum, endNum) {
   if(startNum === endNum) {  
     return [endNum]; 
   } else {  
     let arr =  rangeOfNumbers(startNum + 1, endNum); 
     arr.push(startNum); 
     return arr;     
   }
}

let result = rangeOfNumbers(1,4);
console.log(result);
// [ 4, 3, 2, 1 ]

1.- What happens when the base case is evaluated as false?

The function calls itself:
Steps: 4,6,8

2.- What happens when the base case is evaluated as true?

Returns an array:
Step: 10

3.- The Array, where does it come from?

From the base case:
Step: 10

4.- Why can I push startNum to arr?

Because after the base case is evaluated as true, arr is an array:
Step: 11

5.- Why I’m Getting [4,3,2,1] ?

Because JavaScript uses a “stack” (LIFO, last in first out):
Steps: 10, 13, 16, 19

Cheers and happy coding :slight_smile:

NOTES:

[0] A demo of python tutor:

[1] I also wrote a blog post (it has 27 images)

https://diegoperezm.github.io/blog/recursion.html

[2] If you know spanish, I recorded a video explaining the exercise step by step:

1 Like
7

Fantastic tool pythontutor !!!. It has helped me so much !!!

1 Like
8

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