Cannot understand how Function Recursion Works on this Problem (even if I figured out the solution)

Tell us what’s happening:
Code works fine. There are no problems with execution or whatsoever.
I just cannot understand how this recursion works, on this block:

else { 
  const countArray = countdown(n - 1);
  console.log(`n: ${n}, countArray ${countArray}`);
  countArray.unshift(n);
  return countArray;

The first line that is getting executed is:
const countArray = countdown (n - 1);

which as far as I can tell this the point that the variable recalls the function and as I far as I know, when you use const (constant) you cannot change the variable type.

but still the program continues to the next line where it pushes the next value to the array and after pushing the value the next line is return countArray.

  1. Why doesn’t the function stop at the return?
  2. How it continues after the return and still pushes values?
  3. How does it return the full array?
  4. How does the program/function know how many times the recursion should run?

Is that a feature of Javascript or programming?
Does Javascript have for example, recursion detection?

Your code so far


//Only change code below this line

function countdown(n){
if (n < 1 ) {
  return [];
} else { 
  const countArray = countdown(n - 1);
  console.log(`n: ${n}, countArray ${countArray}`);
  countArray.unshift(n);
  return countArray;
}
}
console.log(countdown(5)); // [5, 4, 3, 2, 1]
console.log(countdown(10));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:73.0) Gecko/20100101 Firefox/73.0.

Challenge: Use Recursion to Create a Countdown

Link to the challenge:
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-countdown

1 Like

I think that this thread is the best so far at explaining what is happening here. A few different people have chimed in with how they explain recursion.

2 Likes

:point_up: but remember that functions resolve to a value: const countArray = countdown(n - 1), countArray is whatever the countdown function resolves to (ie the value it returns) and it’s going to keep calling it until it gets that return value. It doesn’t get to the return value until it hits the terminating condition.

Recursion combined with mutable values, as done here, is incredibly hard to follow, so not understanding it is more than reasonable, it’s an extremely difficult to understand example that’s been chosen.

It’s a feature of maths and almost all programming languages, it’s a basic programming concept.

Yes, sort of, VMs will generally blow up with a too much recursion error or a maximum stack size exceeded if the recursion gets stuck in a loop. Otherwise it’s quite difficult to tell, it’s just a function being called.

3 Likes

I was juust looking at them and thinking about this – one of the issues is that it comes at a point in the curriculum where the primitives that make it much easier to write haven’t been taught: primarily default values, but also I think reverse and definitely concat (rest/spread also makes it a bit clearer imo, but again that’s a bit beyond).

So here (and I’m just writing this concisely here, it would need to be a bit clearer even if this was viable to show):

function countdown (n, output = []) {
  if (n < 1) return output;
  return countdown(n - 1, output.concat(n));
}

IMO use of an accumulator in general is going to make it more explicit: I have what is a loop, and I am using it to put the values into an array, nothing is hidden. The issue with useing push/unshift is that although they allow for the recursion to work without an accumulator, they make it very difficult to track what’s happening.

To deal with default params not being taught, possibly explicitly show it as a loop

function countdown (n) {
  function loop (counter, output) {
    if (counter < 1) {
      return output;
    } else {
      return loop(counter - 1, output.concat(counter));
    }
  }
  return loop(n, []);
}

or i dunno (:grimacing:)

function countdown (n) {
  let output = [];
  function loop () {
    if (n < 1) {
      return output;
    } else {
      output.push(n);
      n = n - 1;
      return loop();
    }
  }
  return loop();
}

I think doing it the way it’s being taught is probably more efficient in JS, but it not simple – in langs that have no loops, almost every time an accumulator is going to be used (and reverse, because normally lists are linked lists, so the value goes on the front not the back for efficiency)

like

let countdown = (n) => {
  let rec loop = (current, output) => {
    (current < 1)
    ? List.rev(output)
    : loop(current - 1, [current, ...output])
  }

  loop(n, [])
}

or

def countdown (n, output \\ [])
def countdown (n, output) when n < 1, do: List.reverse(output)
def countdown (n, output), do: countdown(n - 1, [n|output])
2 Likes

I think that no matter what recursion will take time to ‘stick’ and will generate questions on the forum. The current questions see reasonable to me, but I’ve also felt comfortable with recursion for a decade, so I’m not sure if I’m the best measure.

1 Like

Just add this picture from the other linked thread in our tips or suggestions or whatever. This is a very cool example of explaining what is actually going on.

I never thought I could do that…

5 Likes

I may have cheated but, I started this course time ago and now I am back on track.
Did all over again but, correct me if I am wrong, If I start “Javascript Alghoritms and Data Structure” I dont find any example of the difference between let / const / var. Even if I read article on other sources doesn’t mean they should be provided in examples as I would (and I am) confused seeing something which I don’t know what is and may be crafting theory about it being the “key” to resolve the problem, which is not.
I used this (trick declaring arr outside the function but I guess I got the idea anyway):

//Only change code below this line
var arr=[]
function countdown(n){
  if (n<1){
    return arr
  }
  arr.push(n)
  
  return countdown(n-1);
}
console.log(countdown(5)); // [5, 4, 3, 2, 1]

The picture provided by web-coders is fine but should be done as a comic / meme style as the handwrite is really not something ppl are used to imo. To me I just push the value in the array, then keep call my function until it get to the “base case”/“control case” and the whole array will be returned back

7 Likes

I need to go away and think about this a bit more, but the first of the three is fine and emphasise looping. Then it jumps to this – reading back I’m sorry if I sounded really harsh, I just wanted to emphasise that it is really hard and I think that for a beginner to go from imperative loops to to this could be easier.

Personally, I would want one of

  • have the challenge just console.log something until it terminates, or
  • duplicate one of the loop challenges almost exactly, but use recursion, or
  • sum a value (this is the first challenge, but that seems to just need to change a * to a + afaics?), or
  • duplicate one of the array methods (map?), which would feed into the functional section once a user reached that point (they should maybe be able to recognise that they’ve done the same thing once they hit that point)
  • find a value in an array

I think the last one is best because parsing data structures and finding stuff is what recursion is good at. Then possibly for third one find something in a nested array or object, which is where there is a very practical usecase, and which is made simpler by recursion (well, difficult without a stacks, which is well beyond that part of the course). Anyway, just thinking out loud

1 Like

I had the same confusion with this challenge at first.

This site was really helpful in understanding what was going on:
http://pythontutor.com/javascript.html#mode=edit

Copy and paste the solution in and hit visualize execution and it’ll go through what’s happening.

In a way it’s almost like it’s going backwards. countdown() keeps getting called each time, so it “queries” all of them up until finally it reaches the end value that actually returns something (in this case [ ] a blank array).

Once it gets that blank array, it returns it and works it’s way up. So it starts by returning [ ], then returning [1], then [2, 1] etc…

19 Likes

the best explaination of recursion I’ve found so far is on youtube.

17 Likes

I think adding some building blocks together would be cool. this was my solution using a ternary operator to call a function within a function.

//Only change code below this line
function countdown(n){
function revArr(n){
const countArray = countdown(n-1);
countArray.unshift(n);
return countArray;
}
return (n<1) ? : revArr(n);
}
console.log(countdown(10)); // [5, 4, 3, 2, 1]

1 Like

Hello! After searching google, posting in the forum and reviewing the reply, and reading this thread, still don’t understand the example code. As usually happens when I am having difficulty understanding, read-search-ask only leads to more confusion.

Below is my question and a forum reply, with my comments/questions. I would appreciate any help. Thanks!

can anyone please explain what is happening in the example code (especially after the ‘else’). I do not understand the code even after reading (several times) the explanation provided. In the forum I see a lot of references for how to write the correct solution code but I don’t understand the example code so I’m unable to figure out where to start with the solution. Thank you.

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

Reply

Ethanefung

14h

first think of ‘n’ as 5.
if n is less than 1 then return an array,
else (if the n is greater or equal 1) get the return value of countup(5-1) and push to that value n (which is 5).

what is the value of countup(5-1) in other words countup(4) ?
‘n’ in this context is 4.

if n is less than 1 it return an array,
else (if the n is greater or equal to 1) get the value of countup(4-1) and push to that value ‘n’ ( which is 4).

a question for you.
what is the value of countup(4-1) ?

SolutionReply

Sharad823

14h

Thank you for your response.

first think of ‘n’ as 5. Ok, I understand this
if n is less than 1 then return an array, yes I understand this
else (if the n is greater or equal 1) get the return value of countup(5-1) and push to that value n (which is 5). what is the return value of ‘countup(5-1)’?

what is the value of countup(5-1) in other words countup(4) ?
‘n’ in this context is 4. how does n become 4? n-1 is 4, but how does n become 4? How can n be the same as n-1?

if n is less than 1 it return an array,
else (if the n is greater or equal to 1) get the value of countup(4-1) and push to that value ‘n’ ( which is 4). Again, I don’t understand how the value of n has changed. we called the function with ‘5’ so how can it now be 4? n-1 is 4, but ‘n’ itself is still 5, right?

a question for you.
what is the value of countup(4-1) ? this would be countup(3)

Also - I think .push is used to add to the end of an array, but where are we actually creating the array to add to?

a new function is called, and whaterver is passed in the parenthesis is passed in the parameter n

it is like doing

let a = 5;
myFunc(a - 1);

before the argument is used in the function call, the value is evaluated, and it becomes 4, so whatever is the parameter, the value passed in is 4

So in the new function called, the value of n becomes 4

function myFunc(a) {
 ...
}

when myFunc(a-1) is called, the value of the parameter a is 4 - it has the same name but it is a different variable

countup returns an array, so the array is created in the line const countArray = countup(n-1)

Thanks for your reply. I think I understand that we are saying that the new value of n is n -1. But I don’t understand the logic. In other words, if someone tells me, “use this new value” then I will use the new value; but if I am trying to figure it out on my own, it seems clear to me that if n-1 is 4, then n is 5. So what we are saying is that n and n-1 are the same, which doesn’t make sense to me.

I don’t understand how countup returns an array. The array has to be created somewhere, as in

let fruits = ['Apple', 'Banana']

or

let numbers = [3, 7, 11, 17]

or even an empty array

let array = []

but instead we have

const countArray = countup(n - 1);

which doesn’t create an array as in the above examples. If the array is not created, how can we add to it using .push?

2 Likes

I re-read your example:

let a = 5;
myFunc(a - 1);

before the argument is used in the function call, the value is evaluated, and it becomes 4, so whatever is the parameter, the value passed in is 4

So in the new function called, the value of n becomes 4

function myFunc(a) {
 ...
}

when myFunc(a-1) is called, the value of the parameter a is 4 - it has the same name but it is a different variable.

But I’m still not clear. How can it have the same name but be a different variable? Where does this variable come from? Don’t we have to declare the variable? For example, if we say let a = 5 then a is 5, right? For a to be something different, don’t we need to say ‘let a = a - 1’ in order for a to be 4? I’m also not clear where n fits in, if we are using a.

The array is created in the return [] statement.

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.

4 Likes

let’s take again my example, but I will write it in full in one block

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

in a situation like this, it is common sense to use different names for the variables, to make reading code easier - it works the same tho

in a recursive function, you can’t, so the parameter of the function has always the same name, but different values each time the function is called

we can also see a different example, that can help clear some more recursive functions.

function myFunc(a) {
   return a * 4 + 2;
}

function mySecondFunction(a) {
   let b = "The result is " + myFunc(a+1);
   return b;
}

console.log(mySecondFunction(3));

it is mostly random stuff, an example, I don’t think I would ever use this in real life.
so, there are two functions defined. mySecondFunction(3) is called, and the parameter a gets the value of 3.
Inside this function there is an other function call, and before the string concatenation happens in let b = "The result is " + myFunc(a+1); the function call needs a value, so mySecondFunction stops executing until it gets a value from the other function

so now myFunc is called with the value a+1 passed in, so 4
But also the parameter of myFunc is called a, so the a parameter of myFunc has value of 4 (it is a different a)
so now myFunc execute, returns an output which is used by mySecondFunction to finally continue executing

it is the same thing that happens with recursive functions, only the function calls itself again and again, but with new values each time

1 Like

Thanks for the reply. I’m sorry, I’m completely lost now.