Troubles with Recursion

I have been having some troubles with recursion and can not get it still. I have some doubts:

  1. I can not fully understand what makes the function repeat untill it gets to the base case, I think it’s because of the function is inside the function itself but can not get it completely.

  2. In this challenge that I am right now, I have some issues understanding how the example given turns to be right, because of: a) when I think that a person set “n” to 5 and put it into the formula I get: countArray = countup(5 - 1) = countArray = 4, and if we push that at the end of countArray (countArray.push(n) ), we would get countArrat = [4, 5]. Then if the function repeats, n will be still being 5, so it would return the second time [4, 4, 5] and so on (in my head haha).

  3. I have another issue, in the case of above, when we are given already countArray = [4,5] and the function repeats and excecutes countArray = countup(n - 1), in that moment, would not [4, 5] be errased and be replaced by countup(n = 1). What I mean, doesnt the = makes countArray ONLY be what the last statement say?

Thank you all very much, although I can solve the ecercises given in these challenges, by coping the examples given, I am having so much troubles with this topic and know that if I wanted to make a recursion on a real case escenario, I could not.

  **Your code so far**

// Only change code below this line

function countdown(n){

if (n < 1) {

return [];

} else {

  let countArray = countdown(n - 1);

  countArray.unshift(n);

  return countArray;

}

}

// Only change code above this line

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.45 Safari/537.36

Challenge: Use Recursion to Create a Countdown

Link to the challenge:

yeah it’s a bit confusing but the way I understood this is that -

  1. The function keeps calling itself with (n-1) as input
  2. each time the base case is checked , depending on the base case either it’ll call itself with n-1 or just return from base case (which will happen only once, and in our case it will return [ ])
  3. then first we’ll shift/unshift 1 , then 2, then 3 and so on
    ( according to current setup)

In Java recursion calls varies between 320k and 1024k depending on the version of Java and the system used.
I hope this will help.

Hello @Sebas_16 ,

I can not fully understand what makes the function repeat untill it gets to the base case, I think it’s because of the function is inside the function itself but can not get it completely.

From MDN:

A function can refer to and call itself. There are three ways for a function to refer to itself:

  1. The function’s name

    A function that calls itself is called a recursive function

I wrote a short faq about recursion using the exercise: Use Recursion to Create a Range of Numbers[0].

If you look at the section: 7 (Related topics) you can use those “search terms” to find more information.

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

6.- How can I get [1,2,3,4]?

Replace push with unshift

function rangeOfNumbers(startNum, endNum) {
   if(startNum === endNum) {  
     return [endNum]; 
   } else {  
     let arr =  rangeOfNumbers(startNum + 1, endNum); 
     arr.unshift(startNum);  // <-  here  
     return arr;     
   }
}

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

7.- Related topics:

  • nested (function) calls
  • call stack

Cheers and happy coding :slight_smile:

NOTES:

[0] https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-range-of-numbers

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

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

[2] A demo of python tutor:

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

1 Like

Muchas gracias! Me sirvio mucho tu videooo!

What I dont undestand now is why in the step 4 the code dont just: return [endNum]; , but instead it follows with the else as if the base case is not fullfilled, and after that in steps 11 to 20, it seems that the code somehow saved the past values of startValue and give them back in the result and keep going untill all the given values are treated, that is the part I dont get. What is telling the code to do that?

Hi @Sebas_16,
Sorry for the delayed response, I have not been able to connect.

I think that in general, the problem to understand recursion is (I talk about this in the video) that people belive that the JS code is an algorithm.
The JS code is not an algorithm, is the implementation of an algorithm. This is easier to see if you look at the algorithm used:

 Algorithm:
 if startNum y endNum are equals : 
     finish   
 else:  
     add 1 to  startNum (startNum + 1)

The JS code uses the algorithm plus 2 abstractions:

  • The data structure call stack and
  • Nested (function ) calls

If you don’t understand those abstractions, you can’t understand the JS code.
You can understand the algorithm and recursion, but that is not enough to understand the JS code: because the code is not an algorithm (is an implementation).

What I dont undestand now is why in the step 4 the code dont just: return [endNum]; , but instead it follows with the else as if the base case is not fullfilled,

At step 4:

  • startNum = 2
  • endNum = 4

and after that in steps 11 to 20, it seems that the code somehow saved the past values of startValue and give them back in the result and keep going untill all the given values are treated, that is the part I dont get. What is telling the code to do that?

Again, you are thinking about the algorithm. The JS code is not the algorithm (is an implementation), the JS code uses 2 abstractions: and one is the call stack.

Cheers and happy coding :slight_smile: