Thanks for the reply. I think I understand that we create an empty array for the base case. But why do we need an empty array? And how can we .push a value into countArray when countArray is not an array? And if it is an array, it is different than the empty array created in the base case, right? And if it’s not different, how does it get to be the same array? And how and when do we get to the base case, and what is the point of getting to the base case? I’m not sure what you mean by “this is the power of functions and variables.” What kind of power? Sorry for all the questions but the more I try to understand this the less I understand, and the more confused I am.
2 Likes
We create an empty array so that we can do countarray.push(n). push() only works as an array, so countup() must return an array.
We can .push() because countArray is an array. It is the result of a call to countup(n-1) and countup() always returns an array. The line countArray.push(n) does not execute until the line before it has completed.
It will be an empty array if n is 1 because we will have called countup(0), which returns an empty array. If n is 2, then it will be the array [1] because that’s what countup(1) returns.
The array is returned by the function called in the line const countArray = countup(n-1).
The base case occurs when countup() is called with a value of 1. We need a base case to avoid recursing until our computer crashes.
2 Likes
Look at this code here:
function countdown(n) {
if (n < 1) {
return [];
} else {
const countdownArray = countdown(n-1);
countdownArray.push(n);
return countdownArray;
}
}
The base case (n < 1) returns an empty array.
Otherwise, we call the function again, with the input value n-1. This function call returns an array that we can push the value of n upon before returning the result.
For the scope of this function call, the value of n is one less than the previous value. The function has no knowledge about variables that were defined outside of its scope.
This is the power of functions and variables. The function represents doing an abstract operation on a set of values, and a variable represents a particular instance of an important value. Functions and variables let us repeat the same task and logic for a variety of values.
2 Likes
Thank you, this is helpful.
I’m still not quite understanding how n and n-1 are the same thing (e.g. we call countup(n) with n as 5, then (n-1) is 4, but when we evaluate the base case, n will never be less than one, because n is 5 (since n - 1 = 4). But going along with the voodoo that n = n -1, then I can leap to the following semi-conclusions.
If I’m understanding correctly, using the voodoo above, countup( ) will always return an array because we will always end up at the base case, which returns an (empty) array, correct?
Also, until your clarification, I was not understanding that countArray.push(n) does not execute until the line before it has completed. And the line before it will not complete until we reach the base case, correct?
So if I am correct on the above two points, then we first end up with an empty array once we reach the base case, then countArray.push(n) will execute, right?
So at this point, I am thinking the value of n in countArray(n) would be five, since that is how we initially called the function (before the recursive call), right? So then we would push 5 into the empty array, and end up with [5]. Or maybe we should end up with [0] since that is the last n that we called the function with. But neither of these arrays is the answer we’re supposed to get. So how do we get 1, 2, 3, and 4 into the array with 5, and not get [0] ?
Thanks again for your help.
I understand that the base case returns an empty array, because it’s clearly stated: return []
But I don’t see how anything other than the base case returns an array. How does it return an array? Don’t we need to declare an array, like:
let countArray = ['Apple', 'Banana']
or
let countArray = new array()
Also, if the parameter n is a variable, don’t we need to define the variable somewhere, e.g.
var n = 5;
or if we want to change the value of the variablen don’t we need to state:
n = n - 1;
Also, reading the book Eloquent Javascript, the author mentions the term bindings which is adding to my confusion about the differences (if any) between variables, constants, parameters…bindings. I would appreciate any clarification you can provide. It seems that coding is a practice that requires great precision (GIGO) but I’m finding many explanations out there to be imprecise (vague, conflating, or just plain incorrect) and this is adding to my confusion. The read-search-ask method including reading forum posts usually creates more confusion and questions than clarification, and I do appreciate your clear explanations.
thanks again for the help.
I think you are still getting confused by scope. I’ll try to hit your questions one by one.
Note, I gave code for countup. Corrected here:
function countdown(n) {
if (n < 1) {
return [];
} else {
const countdownArray = countdown(n-1);
countdownArray.unshift(n);
return countdownArray;
}
}
The base case returns an array. That is to say, countdown(0) returns [].
But, countdown(1) returns the 1 unshifted onto the result of countdown(0). That is to say, countdown(1) returns [].unshift(1) or [1].
Now, countdown(2) returns 2 unshifted onto the result of countdown(1). That is to say, countdown(2) returns [1].unshift(2) or [2, 1].
And so on…
countdown(5782) requires the result of countdown(5781) which requires the result of countdown(5780) which requires the result of countdown(5779) and so on all the way down to countdown(0).
The declaration is here
const countdownArray = countdown(n-1)
The variable declaration is part of the function signature. If I have a function
function myFunc(myVar, myOtherVar) {
...
}
the variables myVar and myOtherVar have been defined for the scope of the function.
This is where scope comes in. When we call myFunc() above, the first argument becomes the value of myVar and the second argument becomes the value of myOtherVar.
Calling myFunc(5*7, 89+3) means that while this instance of myFunc() is running, myVar = 35 and myOtherVar = 92. These variables are restricted to the scope of this function call.
Every time I call my function, even when I call my function from itself, the values of myVar and myOtherVar are determined by what values I pass in.
I’m a C/C++ guy. I don’t know about bindings specifically, and they aren’t part of this exercise.
Variables are placeholders for values that are not determined at compile time (@ArielLeslie I’m not sure what the comparable javascript term is here). They get to change.
Constants are placeholders for values that are determined at compile time.
This isn’t to be confused with a const variable, which is a variable whose value is determined at runtime but whose value is not allowed to change for the lifetime of the variable.
Parameters are variables which are function inputs, such as myVar and myOtherVar above.
This might be helpful: JavaScript’s var, let, and const variables explained with a story
1 Like
Thanks for the clarification on scope - parameters have local scope, correct?
Regarding the array, I’m still not understanding it. The empty array is created on the last recursive function call which gives the base case, so that prior to this last function call, we can’t .unshift anything to that (empty) array since it doesn’t exist yet. But the countdownArray.unshift(n) line won’t execute until after the last recursive function call that creates the empty array. So we can only .unshift to the array after this last function call, and n can only have one value at that point, right? So whatever value n has at that time will be unshifted onto the empty array. So we end up with an array with one item in it. Anyway that’s my logic but it’s obviously incorrect.
One more thought - after we create the empty array, we should be done, right? Because we won’t move on to the else statement that includes the .unshift to the array. So it seems to me that we would just end up with an empty array.
Ah, but you are forgetting the functions that called countdown(0) , countdown(1), ect. countdown(5) cannot return until it has the result of countdown(4) and so on.
In recursion, you repeatedly call the function while somehow reducing the input until you reach the base case. You then work back up the call stack, successively building the result until you can return the requested value.
3 Likes
I’m not forgetting, I just don’t understand! What do you mean by “cannot return”? Returning from where? What’s a call stack? What do you mean by working back up the call stack and “building” the “result”? I don’t recall anything about “call stack” having been mentioned in the prior exercises. What is the result and where is it being built? What do you mean by “reducing the input”?
Does the following code make sense to you?
// Function definition for countdown()
function countdown(n) {
if (n < 1) {
// Base case
return [];
} else {
// Recursion
// ToDo: finish the function
}
}
// n = 0 case
let n = 0;
const myArray = countdown(n);
// unshift 1 into the array
myArray.unshift(1);
// log
console.log(myArray);
if so, what about
// Function definition for countdown()
function countdown(n) {
if (n < 1) {
// Base case
return [];
} else {
// Recursion
// ToDo: finish the function
}
}
// n = 0 case
let n = 0;
const myArray = countdown(n);
// unshift 1, 2, and 3 into the array
myArray.unshift(1);
myArray.unshift(2);
myArray.unshift(3);
// log
console.log(myArray);
Hmm. No, neither one makes much sense to me. Or I should say they make less sense to me than the original solution code (if I’m understanding anything about the solution!)
Ok I’ll explain what I think I’m seeing so maybe you’ll be able to see where I’m stumbling.
We declare a function called countdown which takes one argument called n.
Then in the block of the function there is a conditional. If n < 1 it returns an empty array.
If n = 1 or more, the else statement does some recursion and finishes the function somehow.
If n = 0, countdown(0) returns an empty array. So const myArray = .
myArray.unshift(1) adds one to (the front of) the array so console.log(myArray) will log [1] to the console. Then myArray.unshift(2) will add two to the front of the array so console.log(myArray) will log [2, 1]. And so on.
can you tell me what’s confusing in the examples I posted? because once you can understand what’s going on there, recursion will be much easier to understand
this part, above all, as it seems you have difficulties understanding how there can be different n variables with different values
function myFunc(a) { // here we are creating a function that accepts one parameter, the parameter is a variable local to the function, it is called a
...
}
let a = 5; // here we are creating a different variable, still called a, but this exist in the global scope.
myFunc(a-1); // the value a-1 (where a is global variable) is passed inside the a parameter (where a is variable local to the function) of the myFunc function
1 Like
I am still having difficulty understanding scope. I do understand that in your first example,
function myFunc(a)
the parameter a has local scope, meaning that it is local to the function. If I am understanding scope correctly, function parameters always have local scope, correct?
But here I am having trouble understanding what local scope means. I think it means that it only has that value in that particular function. So in the case of the example code from the exercise:
function countup(n) {
if (n < 1) {
return [];
} else {
const countArray = countup(n - 1);
countArray.push(n);
return countArray;
}
}
the parameter n is local to the function. So if we call the function countup(5), then the value of n is 5 inside this funtion, correct? So then we execute the code in the block, which is inside the function, then from inside the function, we call the same function again, so as I see it, the variable n should not change, since we are still within the same function, then we call the same function from inside the function, but it is still the same function. So the value of n should remain 5, which means we will never get to the base case, since n is always 5.
Now I know my understanding as described above is not correct, but it makes perfect sense to me because we still have the same function, so the local variable should remain unchanged in my understanding.
Now BobSmith stated,
“Function variables are scoped within the confines of the function. When you call myFunc(a) , the value that you pass in is the value of a for this instance of myFunc() . If you call myFunc() multiple times with different values, each time the function treats the value as a . This is the power of functions and variables.”
So it seems from his explanation that local scope would mean not just that the variable is local to the function, but for each instance of the function. This is different than what was stated in a prior lesson regarding scope:
“Variables which are declared within a function, as well as the function parameters have local scope. That means, they are only visible within that function.”
So neither your explanation nor the explanation in the exercises talks about each instance of the function, which is what BobSmith states.
Now, the word local to me means something that is restricted to a certain area. e.g. a local bus in New York City would not leave NYC, and similarly, a *local bus" in Philadelphia would not leave Philadelphia. If the bus did leave NYC, it would no longer be a local bus, but maybe an intercity bus. So in this way of thinking, a local variable should be valid within the function. But BobSmith talks about instances of functions, which seems like that local bus (variable) is leaving the area (function) and not only that, coming back as a different bus (variable) which would make no sense from this conception of local.
I do understand that this is apparently not how functions work in reality. So, I can follow the correct way of thinking and do things the correct way because that’s what I’m told to to. However, I’m thinking that programming should be logical yet I’m not finding logic in the correct way. And in programming it seems that we are working with higher and higher levels of abstraction, and I’m thinking, if the fundamentals are not right, everything we build on top of that won’t work. And of course I want to understand this concept of recursion in order to be able to use it in writing programs.
Also, beyond this idea of scope (if I accept what seems to me the voodoo of the correct way of doing things), it still seems to me that we end up with an empty array, because we keep doing the recursive function calls until we get to the base case, which returns an empty array.
BobSmith also mentioned:
“In recursion, you repeatedly call the function while somehow reducing the input until you reach the base case. You then work back up the call stack, successively building the result until you can return the requested value.”
But I don’t see anything about call stack mentioned in the prior lessons and exercises, so I really don’t understand what he means.
Thanks for your willingness to help!
This is the key part that I think is getting in the way of recursion clicking for you.
It doesn’t matter that we called countup inside a function. A function doesn’t know the context in which it is called. It lives in its own world. The key thing here is that it is not the same function in the way you mean. A function is not a single process. It’s a sequence of operations that can happen anywhere at any time. Two instances of a function can be running at the same time. That’s what happens with recursion. Every link in the chain is an independent process on the stack.
Until now, you’ve been working with loops, which are all based on “then go back to the top and do it again”. That’s not what is happening here. The recursive call “const countArray = countup(n - 1)” doesn’t just go up three lines. It is calling a function and waiting for that function to give it a return value. From the function’s perspective it isn’t really different than calling any other function.
1 Like
Thanks for the clarification between recursion and loops, and for the additional explanation regarding recursion. I think this explanation (and a whole lot more) needs to be in the lessons on recursion and functions. I’m still not understanding completely but this is helpful information. After spending a number of hours trying to figure this out, I’m beginning to think the lesson provides a really incomplete and inadequate explanation of recursion, which is unfortunate because, although recursion might be a difficult concept to comprehend, it probably doesn’t need to be this difficult, if only it were explained properly in the lesson (or maybe not at all, at this stage of the curriculum). Quite discouraging - not because of the difficulty in understanding, but of the frustration of the wild goose chase needed to obtain the info the lesson does not provide. thanks again for the help.
Oh - and what is the stack? BobSmith mentioned it in a reply but I don’t think stack is mentioned in any of the prior lessons.
3 Likes
Functions often call other functions. This is called a call stack. It’s just a piece of jargon that translates, roughly, to ‘the list of functions that called down to this one’.
You will also hear about the ‘stack trace’ when you get an error, which is the list of function calls on line numbers which lead to the error message.
Say you have some important pieces of paper, receipts maybe. Every time you get a new one, you put it into the box you use for storing the receipts. Each receipt goes on top of the previous one. You build up this pile of receipts over time. When it comes time to go through them them, you take the first one off the top and review it. Then you take the next one off and so on until you’ve gone through them all.
The receipts are literally a stack. A stack in CS is the same thing. Adding a receipt to the the stack is, in CS jargon, push, taking one off is pop.
Instead of receipts and a box in which you build up a literal stack of papers, in this case you have a set of functions and a chunk of memory. JS adds functions to the stack, then executes them: last function added is the first to be executed.
With recursion you push functions to the stack. Until you reach the terminal case, the recursion just causes more functions to be added to the srack. Once the terminal clause is reached, the last function added executes and resolves to a value. Then the next one executes. Then the next and so on.
5 Likes
You have gone to watch some event in a big hall with many rows of seats. The rows are numbered sequentially from the front, first row is 1, second is 2 etc. You grab a seat somewhere in the middle whilst the person you came with goes to buy some snacks.
The hall fills up pretty fast, and you realise you forgot to check which row you are in. You need to text your friend so that they can find you.
To solve this, you pass a piece of paper and a pen to the person in front and explain the following rules:
- if they don’t know the row number, pass the paper & pen forwards to the person in front and explain the rules to the person they’ve passed it to.
- if the person in possession of the paper & pen knows the row number, to write it on the paper and then pass back to the person behind.
- if they receive the paper & pen from the person in front of them, they need to increment the number before passing back to the person behind.
So you pass the paper forwards. It works its way forward until it reaches the very front row (for some reason no-one knows which row they’re sitting in). The person in the front row writes “1” on the paper, passes it back. That person behind changes it to “2”, passes it back. And this continues until it reaches you, and you add one to the number on the paper, and you can text your friend with the correct row number.
3 Likes
Thank you @DanCouper, this is helpful.
I can’t imagine being able to understand recursion without understanding the “call stack” which, if I am understanding correctly, is not just a concept but something that exists in reality (i.e. a chunk of physical memory) - which, I am sure, is why @JeremyLT mentioned it.
While it might not be possible to mention in the curriculum all the different ways of conceptualizing recursion (a few examples of which you have provided), it seems imperative to mention the call stack, since it is not just a concept but something that actually exists, and without which JS recursion would not work as it does (e.g. last in first out). Also, reading the functions chapter in the book Eloquent JavaScript (recommended I think by @ilenia), I see that the call stack is mentioned before recursion, and the section on recursion references the call stack.
Each person’s mind works differently I am sure, but the call stack is not human so I would think it works the same way every time. So up to now I have relied on my own (uniquely distorted, mutating and fluid?) mind to conceptualize recursion, but it turns out there is an actual concrete way that the physical memory processes the recursive functions, so it seems to me that understanding how the call stack works is fundamental to understanding recursion.
But the call stack was not mentioned at all in this lesson or in the JS curriculum up to this point. I cannot fathom why not, if the idea was for students to actually understand recursion and not just churn out the solution code (which I was able to do without really understanding how recursion worked).
4 Likes