Why .unshift (n-1) when decreasing numbers

daniel_Landau · April 29, 2022, 11:40pm

Hi Campers,
Thanks again for your invaluable help.

I just don´t understand in this challenge, why should I use .unshift (add at the beginning) when I suposse to build the array decreasing numbers.

When I have:

const countArray = countdown(n - 1); countArray.unshift(n)

Let´s say we Start with n = 5
[ 5 ]

Then
countdown(n-1) >>> (5 -1) = 4
countArray.unshift(4)
[4, 5]

countdown(n-1) >>> (4 -1) = 3
countArray.unshift(3)
[3, 4, 5]

countdown(n-1) >>> (3 -1) = 2
countArray.unshift(2)
[2, 3, 4, 5]

countdown(n-1) >>> (2 -1) = 1
countArray.unshift(1)
[1, 2, 3, 4, 5]

countdown(n-1) >>> (1 -1) = 0
if (n < 1) {return

Why shouldn´t I push those results when I try to countdown?

I also read that other students have problems to understand where the array is declared, and I guess that once you start
(unshifting) or (pushing) arguments, automatically turns into an array.
Is that so?

  **Your code so far**


// Only change code below this line
function countdown(n){
if (n < 1) {return [];}
else {const countArray = countdown(n - 1);
countArray.unshift(n);
return countArray;}}

console.log(countdown(-1));
console.log(countdown(10));
console.log(countdown(5));
// Only change code above this line

  **Your browser information:**

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

Challenge: Use Recursion to Create a Countdown

Link to the challenge:

a_aramini · April 29, 2022, 11:58pm

the unshift method adds items to the beginning of the array.

So if you start with values 1,2,3,4,5 and unshift() them one-by-one into an array in that order, and then iterate through the array starting at index 0 the numbers will be in the array in this order…

5, 4, 3, 2, 1

the push() method adds new items to the end of the array… so you’d get

1, 2, 3, 4, 5

so you would either have to iterate through the array starting at index 4 or index 0 depending on the order you want to return the numbers from the array, not into the array.

But I think that is just part of what the challenge is trying to demonstrate.

In recursion, the function keeps calling itself until it hits the base case and then ends. Otherwise it might keep calling itself forever (like an infinite loop) or stop calling itself prematurely (giving incorrect results).

Recursion is a difficult concept to grasp for most people the first time they are introduced to it. So I think the challenge is trying to use a very simple example to illustrate it as clearly as possible.

As far as the “countdown”, I think they are just referring to the order you are storing the numbers into the array, not the order you are pulling them out. The main focus here is recursion, not the push or unshift methods

remember that arrays in Javascript are 0 indexed (first item starts at index 0)

the line const countArray = countdown(n - 1);

sets up, or declares the array.

push() and unshift() just add to the array after all the recursion calculations have been done and the base case has been reached.

Per the challenge instructions…

countdown(5) should return [5, 4, 3, 2,1]

I think you are confusing the example in the challenge with the challenge instructions

use the appropriate method to achieve the desired results

daniel_Landau · April 30, 2022, 1:47am

Thanks a_aramini,

Since:

I guess my thought were right. I should have used .push to obtain conuntdown, and I don´t know why the Challenge asks for . unshift, and gives a decreasing order.

colinthornton · April 30, 2022, 1:56am

I think you’re misunderstanding the order of the unshift calls in the code you posted. The first item added to the array with unshift is 1, not 5.

countdown(5) needs to get the result of countdown(4) needs to get the result of countdown(3) needs to get the result of countdown(2) needs to get the result of countdown(1) needs to get the result of countdown(0) which is [], then unshift 1 to that, then unshift 2 to that, then unshift 3 to that, then unshift 4 to that, then unshift 5 to that.

a_aramini · April 30, 2022, 2:06am

EDIT: My initial explanation and info in this reply was dubious at best and needed editing and hopefully has been fixed to explain it correctly

Please see this reply and this reply for further clarity.

I got that backwards by mistake and have corrected it in the original reply.

Generally it is not about increasing or decreasing order. It is about what is the insertion point where items are being placed into the array.

Well, I should say, we do care about the order in which the recursive part of the function is going to return the values it calculates to the method, because that will dictate what method we need to choose to accomplish this.

By definition…

The unshift() method inserts them each at array[0] (the start of the array).

The push() method inserts them each at array[array.length - 1] (the end of the array).

We are in the context of a very specific recursion function, so unshift()will give us the correct order, and push() will reverse the order.

edit: [ The recursion calculations happen first starting from 5, but these calculated values of n are stored in what’s called a stack. The values are pulled off the stack when the recursion is done, in First In Last Out order… so 1, 2, 3, 4, 5 in this case. So you need to use the correct method to account for that and end up with an array that meets the requirements of the challenge. ]

The challenge is introducing us to the above methods, but is also introducing us to and demonstrating recursion…

Lets say we want to write a function that will work for any given array length. We won’t necessarily know the length before hand. We just know that the index of the last item in that array will be arr.length - 1, so let’s refer to the unknown length, arr.length, as n.

So to get all the elements in an array of n length, how could we write a recursive function that works in a general case of an array of n length?

Remember, the recursion is “counting down” from 5 to to end up at 0.

Using the info we know for an array of n length, we know we are done when we hit 0 because we’ve gone through all of the possible items that can be stored in the array.

You can have an array of length 0, but an array of length zero minus one, or “negative 1”, doesn’t really make much sense.

Remember that…

The value of the length of an array is always going to be the index number of the item at the end of the array plus one (array[last_item_index] + 1 ) because arrays are 0 indexed.

The index of the last item in the array is always going to be the value of the length of the array minus 1 (array.length - 1 ), again because arrays are 0 indexed.

Both are saying the same thing, I know. But it’s a matter of context and perspective and if you mix this up, you make errors like I made and had to fix in my initial replies… off-by-one errors or mixing up order of things if you’re dealing with multiple things like recursion, unshift(), etc., all at the same-ish time (people do it all the time, as I had done earlier).

So because of what we know from above, we know that our base case test to end the recursion needs to be when n -1 = 0, or when n = 1 … (1 - 1 = 0)

We will test for the base case condition in our function first. If that condition hasn’t been met, we want the recursion to keep going until the condition is met.

If we call our function with a parameter of 5 for an array of length 5 then we’d expect our function recursion to go like this :

BEGINNING OF EDIT

This section of the reply has been edited to correct some errors and oversights

function(5)

n = 5, ( n -1 ) = ( 5 - 1 ) = 4
n = 4, ( n - 1 ) = (4 - 1 ) = 3
n = 3, ( n - 1 ) = (3 - 1 ) = 2
n = 2, ( n - 1 ) = (2 - 1 ) = 1
n = 1, ( n - 1 ) = (1 - 1 ) = 0 <— Base Case, recursion stops

we should expect to get all the indexes starting from 4 to 0 (4, 3, 2, 1, 0) and we could then use those indexes to get the values associated with those indexes.
arr[4], arr[3], arr[2], arr[1], arr[0].

The paragraph above is crossed out because it incorrect, or at least out of context and not applicable here. The recursion is not calculating array indexes, it is generating the array values.

I don’t know what I was, or if I was, even thinking there.

It’s like all of the sudden (due to lack of sleep, coffee, or whatever) my mind totally and randomly drops the idea of recursion all together and I begin to speak as if we are just pulling items out of an already created array and the recursion and unshift() never happened.
lol

My apologies for that.

END OF EDIT

You’re focusing on unshift() vs push(). The point is to understand recursion and how it can be useful when we want to write a function in a generalized way but we don’t know what the given parameter might be.

daniel_Landau · April 30, 2022, 3:16am

Thanks colinthornton and a_aramini

Let me see if I am Close to understanding it:

When we have n = 5
countdown(n-1) >>> (5 -1) = 4
countdown(n-1) >>> (4 -1) = 3
countdown(n-1) >>> (3 -1) = 2
countdown(n-1) >>> (2 -1) = 1
countdown(n-1) >>> (1 -1) = 0 (n < 1) {return}

a) Only when it finishes that first function is that it starts the Second, to unshift ?
Is that so?

Thanks. I didn´t know that.

b) Is that above the reason why the first item added to the array in this case will be 1 ?

So, I guess now it takes place the Second function:

[1]
[2, 1]
[3,2,1]
[4,3,2,1]
[5,4,3,2,1]

c) Is that what it is doing ?

Definitely.
Trying hard here and I hope this helps other as well. Many thanks.

a_aramini · April 30, 2022, 3:45am

EDIT: I’ve edited this reply to correct an erroneous explanation.
Please see this reply and this reply for a better explanation

Below was edited to correct erroneous info:

yes, so the number on the left for the recursion calculations are the array values 5 … 1

All of the recursion calculations take place first, until it reaches the base case.

Every time the function is called and performs a calculation, the results of that calculation, in this case (n-1), is stored in an internal stack. A stack is a type of data structure.

The recursion function creates the stack on the fly because it has to keep track of the results of each calculation somewhere, and it hasn’t got to the unshift() or push() part of the function block yet. This stack is internal to Javascript (abstracted from the programmer).

This is why the first value to populate the array is 1, and then 2, then 3, then 4, then 5. This is regardless of whether you use unshift() or push().

Those methods only determine where the value is placed in the array, not what the value is.

They values from the stack are push()ed or unshift()ed to the array in the order they are pulled off the stack. Since the stack is FILO (First In Last Out), 1 comes off of the stack first.

…

Starting from 1, unshift() does this (for that particular function in that challenge…

[ 1 ]
[ 2, 1 ]
[ 3, 2, 1 ]
[ 4, 3, 2, 1 ]
[ 5, 4, 3, 2, 1 ]

and push would do the opposite…

[ 1 ]
[ 1, 2 ]
[ 1, 2, 3 ]
[ 1, 2, 3, 4 ]
[ 1, 2, 3, 4, 5 ]

but that’s not what we want for a “countdown”

a_aramini · April 30, 2022, 3:51am

So in the “real world” the challenge is how would I come up with a function that is recursive and works for all cases, and what would it look like?

In the “real world” you are not always given a nicely packed data set or array or whatever, you often have to build it yourself from scratch.

Luckily, most the time we have while or for loops and don’t have to worry about recursion. But there are cases where it is a solution, so a programmer should know how or at least have been exposed to the concept.of recursion.

There have been debates in Computer Science circles about whether it is more efficient than loops, but I’m not a CompSci major, so that’s “above my pay grade”

a_aramini · April 30, 2022, 3:09pm

EDITED due to a total mind fart failure on my behalf…

@colinthornton

~~No, the first item added to the array with unshift would be 4 (for the function in this case).~~
~~We are starting with 5, remember? and 5 -1 = 4.~~
~~Then we unshift() 4 (which puts it at the beginning of our array which starts out in the very beginning, before we call the function with 5, as:~~
~~[ ]~~
~~Then our initial value (5) is passed to the function, so we have:~~
~~[5]~~
~~Then (5-1) is passed to the function. 5-1 = 4 so now we have:~~
~~[4, 5]~~
~~Using unshift() vs push() just affects whether the 4 value the item is being placed into the array goes at the beginning or at the end of the array.~~
~~We are “counting down” from 5, not “counting up” to 5. The first value we push or unshift after our initial value of 5 will be 4 regardless of which array method we use.~~

~~Don’t confuse the indexes with the values, I know it’s easy to do and there’s a lot going on there and a lot to wrap our head around.~~

Well, why don’t you listen to your own advice there Mr. a_aramini! Are you thinking about the stack and then typing about the array? Shame on you! lol… and get some sleeeep!!! lol

NEEEEEED SLEEEP!!! ERROR! ERROR! CANNOT COMPUTE… .CANNOT COMPUTE… ERROR! ERROR!.. a_aramini CANNOT COMPUTE…

The crossed out parts are wrong… I corrected it below for whoever might not know this and for the benefit of future readers…

A full night’s rest later…

You are indeed correct @colinthornton

All of the recursion calculations take place first…

We start with n = 5, and that gets put on the stack.

Think of the stack like a box or bucket, items can only go onto the top of the stack and be pulled off the top of the stack.

The stack:

| 5 | <— Top of stack

Then ( n - 1 ), n is 5 so: ( 5 - 1 ) = 4

The stack:

| 4 | <— Top of stack
| 5 | <— Bottom of stack

Then ( ( n -1 ) - 1 ), so: ( ( 5 - 1 ) - 1 ) = 3

The stack:

| 3 | <— Top of stack
| 4 |
| 5 | <— Bottom of stack

Then ( ( n -1 ) - 1 ), so ( ( 5 - 1 ) - 1 ) = 3

The stack:

| 3 | <— Top of stack
| 4 |
| 5 | <— Bottom of stack

Then ( ( ( n -1 ) - 1 ) - 1 ), so: ( ( ( 5 - 1) - 1 ) - 1 ) = 2

The stack:

| 2 | <— Top of stack
| 3 |
| 4 |
| 5 | <— Bottom of stack

Then ( ( ( ( n -1 ) - 1 ) - 1 ) - 1), so: ( ( ( ( 5 - 1) - 1 ) -1 ) - 1 ) = 1

The stack:

| 1 | <— Top of stack
| 2 |
| 3 |
| 4 |
| 5 | <— Bottom of stack

Then ( ( ( ( ( n -1 ) - 1 ) - 1 ) - 1) - 1 ), so: ( ( ( ( 5 - 1) - 1 ) - 1 ) - 1 ) - 1 ) = 0

The stack remains unchanged, we didn’t store the base case it is just a limit placed on the recursion to keep it from going to infinity or ( - infinity in this case)

| 1 | <— Top of stack
| 2 |
| 3 |
| 4 |
| 5 | <— Bottom of stack

We’re at the base case now, so bail out of the recursion stuff, forget about the 0 value, we don’t need it… lets move to the next part of the function body block.

Now we get to the unshift() part, where we start pulling values off the stack.

unshift( 1 )
array = [ 1 ]

Stack:

| 2 | <—Top of stack
| 3 |
| 4 |
| 5 | <— Bottom of stack

unshift( 2 )
array = [ 2, 1 ]

Stack:

| 3 | <—Top of stack
| 4 |
| 5 | <— Bottom of stack

unshift( 3 )
array = [ 3, 2, 1 ]

Stack:

| 4 | <— Top of stack
| 5 | <— Bottom of stack

unshift( 4 )
array = [ 4, 3, 2, 1 ]

Stack:
| 5 | <— Top of stack

unshift( 5 )
array = [ 5, 4, 3, 2, 1 ]

Stack:

|empty| ← memory pointer/references to stack not needed, memory reallocated via garbage collection

(all this is stack stuff is internal to JavaScript, the programmer need not worry about it, other than to know it exists and that the behavior affects the order unshift() or push() or whatever_method() will receive the values, methinks)

Using unshift() vs push() just affects whether the being pulled off the stack is is being placed at beginning of the array, or at the end of the array.

Lego_My_Eggo · April 30, 2022, 6:29pm

Watch the code being run, the base case returns an array, then the first thing added is 1.
watch it run

a_aramini · April 30, 2022, 8:46pm

@Lego_My_Eggo
OH, yeah,… you’re right. DOH! Sorry, my bad! Yeah I got that mixed up (see, I told ya recursion is tricky and hard to grasp ). My brain was thinking indexes and index values, but I forgot to consider that all the recursion calculations take place first.

There is another piece to the puzzle, which I don’t think is explained in the challenge. There is an internal stack being created on the fly and used by the function to store/keep track of the calculated values of n which is abstracted from the programmer. So to answer the question of, “Why is 1 the first value to be placed into the array?”…

… well the stack order is why. There’s no “magic tricks” going on there.

(I will have to go back and look through the recursion challenges to see if they ever mention anything about a stack).

The stack is FILO (which means First In Last Out). Unlike an array, stuff can only be put onto and taken off of the stack in one direction (from the top). Whereas you can insert values into an array anywhere, using an index. Every item placed on the stack pushes the item before it down on the bottom of the stack.

When it is finished with the recursion (the “looping mechanism”) because it has reached the base case, it pulls the values off the stack and then the unshift()-ing happens.

5 was the first value to go into the stack (where the calculated recursion values are temporarily being stored) so 5 is the last to come out of the stack and into the array. So it pulls 1 off the stack, then 2, then 3, etc.

The value stored at index 0 is changing due to the unshift()ing. Since we are using the unshift() method, we are always in the context of index 0 ( countArray[0] ) in regard to countArray.

I thought it through some more and here is a visual to show what is actually happening…

Good catch of my oversight which led to that error in my explanation.

I will edit previous replies to refer to this reply so as not to lead anyone astray with incorrect information. My apologies to @colinthornton and @daniel_Landau

That is actually a great challenge for introducing recursion and push() and unshift(). It really makes you think hard, and at times I was typing push when I meant unshift and vice versa, and referring to the array when I meant stack. So much going on there… easy to get tripped up! Especially since I haven’t done those challenges in a while

Also, see this reply for a step-by-step explanation

Lego_My_Eggo · May 1, 2022, 5:32am

Looks like you got it now. This is why it can be such a hard time learning recursion because you really have to know about the stack and how function calls have to wait and be run before they actually become a value you can use. Which is why people get tripped up on where the array comes from. Or how you are push/unshifting to something that doesn’t look like an array in the code, but becomes an array later.

a_aramini · May 1, 2022, 5:44am

I learned recursion in the past, but hadn’t really used it much. It had been quite a long time since then so the concept got dusty and rusty.

Mathematically, I understood the recursion. Yes, the stack part was throwing me off. I knew it had to be temporarily storing the calculations in memory somewhere… then it clicked… duh, the stack!

I wasn’t having the issue with the recursion itself so much as rather I distracted myself by thinking about indexes and trying to explain it to the OP. I picked a bad premise and then started digging a hole lol. Anyways… I’ve butchered this whole thread enough for now

Thanks again!

colinthornton · May 1, 2022, 11:57am

One clarification, the way you’re writing it sounds like values of n are being put on some stack, but that’s not the case. Rather countdown function calls are being placed on the call stack.

a_aramini · May 1, 2022, 12:32pm

Yes, that’s what I’m referring to. I didn’t just learn about the concept of a stack, I’ve learned it before. I had just forgotten about it until this recursion challenge discussion and your link to the code visualizer triggered my memory. BTW that’s a cool link… I’ve used that before too when I was learning python on another site some years back… but had forgotten about that too. lol

I am aware that there are different stacks used for different purposes. I know there’s also distinctions, some of which are subtle. Ultimately up the chain there’s references/pointers to somewhere in physical memory just like any other stack, heap, variables, arrays, … objects, etc., may have, right?

Then there’s the all the hardware… CPU/ALU/MU/CU, registers and cache, etc.

But I’m not even close to well versed enough on how any of that stuff works, to try to explain it without a lot of research. I’m not a Comp Sci major, I am just aware that this kind of stuff exists.

I didn’t want to get too deep into the weeds (which I already have anyways thanks to my OCD lol) with all of that either as that’s mostly abstracted in modern HLL languages I think. If I remember correctly, in Assembly languages, ANSI C , etc you have to worry about that stuff and perform garbage collection and all that kind of stuff.

I already said way too much in other replies lol

I really just wanted to illustrate the concept of a “stack” to drive the point home because I felt like I initially grossly mislead the OP and I wanted to correct that deliberately and promptly. Also, I didn’t want others who might read this thread in the future to be mislead either.

Thanks, good link!

a_aramini · May 2, 2022, 12:24am

Having a hard time letting this go… lol.

What would be a better way to visually illustrate a call stack to someone not familiar with the concept?

The wikipedia and other sites seem kind of complex (I’m aware that it can be a complex topic) in their explanation and that might confuse newbies who aren’t used to reading technical docs.

Asking for future reference… like if you have any good links with good visuals
that could just be dropped, rather than me trying to personally translate a web doc into my own words in a forum reply… lol

Thanks

colinthornton · May 2, 2022, 12:55am

I think the execution visualization that @Lego_My_Eggo posted above is a great representation. It lists all the calls on the stack in the “frames” column with the function name, and lists the variables within their scopes.

With this it’s easy to see that each invocation of countdown is put into a separate context.

JeremyLT · May 2, 2022, 12:58am

Two small points.

Technically, garbage collection is one type of automatic memory management. C uses manual allocation and deallocation.
This is true for all versions of C, not just ANSI C, which is a very old version that has been replaced largely by C99 or a later standard.

a_aramini · May 2, 2022, 1:00am

Honestly I was just throwing around terms there that I don’t have any personal experience with. The idea is there but I lack the deeper knowledge to be more precise… thanks!

a_aramini · May 2, 2022, 1:12am

I took a semester of C in the late 90’s at community college circa 98, where we were introduced to these things, but obviously 1 semester over 20yrs ago is not gonna cut it now. It was probably C99 or whatever was just before that.

I still have a copy of MS Visual Studio C++ 6.0 on floppies if anyone is interested!