countDown challange - recursion solution #2

[MSPa1nT]

Hej!

I’m really having problems wrapping my head around recursion as i have to spend several hours to understand the core concept and is unable to come up with recursion solutions when requested, which is challanging.

My questions is related to the countDown challange (https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-countdown) , where one of the solutions is as follows;

function countdown(n){
return n < 1 ? : [n].concat(countdown(n - 1));
}

Could someone help me understand better how this is working?
When i enter it into JavaScript Tutor - Visualize JavaScript code execution to learn JavaScript online
i only see that it works its way down and evaluating n for each call (n =5, n=4,n=3…) and once it hits n = 0 it return an empty array.

In my head this means that this is feed into the call of countdown(1):

(countdown (0) {
return )
→ countdown(1){
return [1].concat[countdown(0)]) ( == return [1].concat() )

although when i try to do this syntax in the terminal it gives me an error which leads me to believe that i dont quite comprehend what is happening, and how.

all help and input on how to further get better when it comes to recursion is highly appreciated. I’ve searched and watched prettty much all youtube videos on the subject allthough they usually talk about the same type of thing (fibonacci, countdown, search-boxes) and go through the code , although it always feels like there is some core fundamentals missing.

Essentially same with the challange afterwards (range of numbers : freeCodeCamp Challenge Guide: Use Recursion to Create a Range of Numbers) where the #2 solution goes as:

function rangeOfNumbers(startNum, endNum) {
return startNum === endNum
? [startNum]
: rangeOfNumbers(startNum, endNum - 1).concat(endNum);
}

Absolutley mind boogled how the calling and everything works for this solution.

[sanity]

That looks correct, for n = 1, it’s
[1].concat(countdown(0)) → [1].concat([]) → [1]

Essentially this solution can be written as

function countdown(n){
  if (n < 1) {
    return [];
  } else {
    const curArray = [n];
    const recursed = countdown(n - 1);
    return curArray.concat(recursed);
  }
}

Just with few steps made explicitly.

I’m going to say those one line solution can be confusing, not necessarily from the recursion parts. Lots of the confusion can be added with the way they are written. Unless you look all the time at such expressions it will take more time to figure out what exactly is happening, comparing to a slightly more verbose solution.

[twotani]

Perhaps the illustrations help. The recursive function keeps calling itself with a different argument and eventually the recursion stops (reaching the end case), and the value is returned to the caller(s) building up the final answer as they return.

[MSPa1nT]

Thanks for your in-depth answers guys <3

I noticed now that the syntax below actually worked, and does not generate a syntax error.
[1].concat([]) // [1]

Could you help me understand below step , as visualized with javascript tutor:

It looks to me in this step that the empty array is returned immediately to the first call instead of a trickling-down in the stack. Is this just me misinterpreting it or is there anything else to it which they mean to illustrate by making the final step (n = 0) immediately return the array to the start of the original calling function?

[jaket]

Hello MSPa1nT,

I wrote this one yesterday but the system limits how many posts as I just joined.

This might help you out - explain it a little differently.

I have expanded out the example you have given.
Added a few comments and console.logs.
Added helper parameter to see how many times the countdown function has been called.

// Only change code below this line
function countdown(n, iteration){
  if(typeof iteration === 'undefined'){
    iteration = 1;
  }
  else{
    iteration++;
  }

  if(n < 1){
    return [];//return empty array
  }
  let initArray = [n]; //initial array item
  console.log('initArray:', initArray, 'iteration:', iteration);
  
  let nextArrayItem = countdown(n - 1, iteration); //next array item - recursion happening here
  console.log('nextArrayItem:', nextArrayItem, 'iteration:', iteration);

  let returnArrayItem = initArray.concat(nextArrayItem);
  //console.log('returnArrayItem:', returnArrayItem, 'iteration:', iteration);

  return returnArrayItem;
}
// Only change code above this line

console.log('what is countdown(5):', countdown(5));

Now here is the resulting console.log you would get:

initArray: [ 5 ] iteration: 1
initArray: [ 4 ] iteration: 2
initArray: [ 3 ] iteration: 3
initArray: [ 2 ] iteration: 4
initArray: [ 1 ] iteration: 5
nextArrayItem: [] iteration: 5
nextArrayItem: [ 1 ] iteration: 4
nextArrayItem: [ 2, 1 ] iteration: 3
nextArrayItem: [ 3, 2, 1 ] iteration: 2
nextArrayItem: [ 4, 3, 2, 1 ] iteration: 1
what is countdown(5): [ 5, 4, 3, 2, 1 ]

Why would the console.log messages be coming out in that order?
Now that is the tricky part to get your head around.

If you match up the iteration number with initArray and nextArrayItem - what would you get it the arrays where concatenated?

Did you get it yet?

So what is happening when you call:

countdown(5);

Lets step through it.
First of all it calls countdown with parameter value of 5 - iteration 1.
When 5 is sent in it will create initArray and get nextArrayItem.
But to get nextArrayItem, need to call countdown again with value 4 - iteration 2.
When 4 is sent in it will create initArray and get nextArrayItem.
But to get nextArrayItem, need to call countdown again with value 3 - iteration 3.
When 3 is sent in it will create initArray and get nextArrayItem.
But to get nextArrayItem, need to call countdown again with value 2 - iteration 4.
When 2 is sent in it will create initArray and get nextArrayItem.
But to get nextArrayItem, need to call countdown again with value 1 - iteration 5.
When 1 is sent in it will return [ ].
This is iteration 5 - so return [ ] for nextArrayItem, from the countdown call of countdown(1)
When initArray[1] nextArrayItem is [ ] when concat get [1] - iteration 5.
When initArray[2] nextArrayItem is [1] when concat get [2, 1] - iteration 4.
When initArray[3] nextArrayItem is [2, 1] when concat get [3, 2, 1] - iteration 3.
When initArray[4] nextArrayItem is [3, 2, 1] when concat get [4, 3, 2, 1] - iteration 2.
When initArray[5] nextArrayItem is [4, 3, 2, 1] when concat get [5, 4, 3, 2, 1] - iteration 1.

Hope that makes sense - as I said, its a tricky one to get your head around

[MSPa1nT]

Thank you very much for the detailed explanation and overview Jaket, although I’m afraid that it isn’t really making it more clear to me. Could you clarify what you mean when you say :

“If you match up the iteration number with initArray and nextArrayItem - what would you get it the arrays where concatenated?”

I think my main challange is that I don’t understand the fundementals of it which makes it difficult for me to visualize in my head the process and the way to go about for solving taks which requests recursion to be used , which is really frustrating. I think i need more practice essentially. Do you know where there is more of these recursion challanges that one can take to practice ?

[jaket]

Hello MSPa1nT,

Possibly match up - may not be the best way to put it.

But if you look at resulting console.log

The question really is - Why is the iteration 1 at the top and also at the bottom?

Why is it not like this?

initArray: [ 5 ] iteration: 1
nextArrayItem: [ 4, 3, 2, 1 ] iteration: 1
initArray: [ 4 ] iteration: 2
nextArrayItem: [ 3, 2, 1 ] iteration: 2
initArray: [ 3 ] iteration: 3
nextArrayItem: [ 2, 1 ] iteration: 3
initArray: [ 2 ] iteration: 4
nextArrayItem: [ 1 ] iteration: 4
initArray: [ 1 ] iteration: 5
nextArrayItem: [] iteration: 5

As nextArrayItem is populated by the return value from the countdown function.

The following line of code is the recursion bit:

let nextArrayItem = countdown(n - 1, iteration); //next array item - recursion happening here

so if you look at the countdown function
the first return value for nextArrayItem happens after

initArray: [ 1 ] iteration: 5

So think of it like this - if it was not calling itself - the coundown function would be repeated in this section (not just once but for how many times it gets to this stage of the function).

Not sure if I made that any clearer.

Found this link via google - it might help:

• https://betterprogramming.pub/understanding-recursion-with-examples-f74606fd6be0

[MSPa1nT]

Thanks alot Jaket, you’re explanations are top tier , 10/10.
I will investigate this topic a bit more and review the link you sent me and then come back to this now and again to make sure I’ve understood it 100%

im 100% with you on the iteration part and how it’s connected in your code. Due to the fact that the [n] is stored in the call stack for each countdown(n) and the thread of execution trickles down as the stacks are being removed , the iteration will go from 1 → 5 → 1.

[jaket]

good to hear it is getting a bit clearer - it is a tricky one to explain

Possibly check out recusive tree structure - it might help in picturing in you head

[jaket]

Hello MSPa1nT,

I just remember about cte (common table expressions), they can be used in recursive manner - database stuff.

This link might help with explanation examples:

• Understanding SQL Server Recursive CTE By Practical Examples