recursion: storage of multiple values in variables

Question

Code shows a recursive function that takes a number, say n=5, and returns an array counting down from n to 1 i.e [5,4,3,2,1].

My confusion lies right before we push the numbers/values of n to countArray. My understanding is that countup(n - 1), will generate numbers (say n=5) 5,4,3,2,1...but I don't understand where/how they are stored. I would have thought n would end up as its last defined value, n=1, or a blank array. But that's not true and they are somehow all pushed into an array that in my understanding was never created/defined prior to pushing into it. So those two lines with comments are the two I need help understanding.

tl;dr: (1) how are the values 5->1 stored without overwriting to the final value 1, prior to being pushed into the array? (2) Where/how was countArray defined as an array before we push into it;

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);  //the storing of 5,4,3,2,1 I don't understand
    countArray.push(n); //I don't understand when countArray was defined as an array
    return countArray;
  }
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

edit: this post's title probably need changing to array rather than variable or etc.

Answer 1

Perhaps adding some logging might make it more clear.

We can add a simple logger that reports the values like this:

Calling with 5
|   Calling with 4
|   |   Calling with 3
|   |   |   Calling with 2
|   |   |   |   Calling with 1
|   |   |   |   |   Calling with 0
|   |   |   |   |   Returning [] (base case)
|   |   |   |   Pushing 1 to []
|   |   |   |   Returning [1]
|   |   |   Pushing 2 to [1]
|   |   |   Returning [1,2]
|   |   Pushing 3 to [1,2]
|   |   Returning [1,2,3]
|   Pushing 4 to [1,2,3]
|   Returning [1,2,3,4]
Pushing 5 to [1,2,3,4]
Returning [1,2,3,4,5]

So the array was defined in the base case. Then as we worked our way back up the call stack, we added to it. There are alternative ways of doing this, but this is one common and reasonable way to go about it.

You can see how I added the logging in the following snippet:

const log = (depth, message) => 
  console .log ('|   '.repeat (depth - 1)  + message)


function countup(n, depth = 1) {
  log(depth, `Calling with ${n}`)
  if (n < 1) {
    log(depth, `Returning [] (base case)`)
    return [];
  } else {
    const countArray = countup(n - 1, depth + 1);  //the storing of 5,4,3,2,1 I don't understand
    log(depth, `Pushing ${n} to [${countArray}]`)
    countArray.push(n); //I don't understand when countArray was defined as an array
    log(depth, `Returning [${countArray}]`)
    return countArray;
  }
}

countup(5)

.as-console-wrapper {min-height: 100% !important; top: 0}

Update

Perhaps clearer would be this result:

/ Calling with 5
|   / Calling with 4
|   |   / Calling with 3
|   |   |   / Calling with 2
|   |   |   |   / Calling with 1
|   |   |   |   |   / Calling with 0
|   |   |   |   |   \ Returning [] (base case)
|   |   |   |   | Pushing 1 to []
|   |   |   |   \ Returning [1]
|   |   |   | Pushing 2 to [1]
|   |   |   \ Returning [1,2]
|   |   | Pushing 3 to [1,2]
|   |   \ Returning [1,2,3]
|   | Pushing 4 to [1,2,3]
|   \ Returning [1,2,3,4]
| Pushing 5 to [1,2,3,4]
\ Returning [1,2,3,4,5]

Which only involves a minor change to the logging statements:

const log = (depth, message) => 
  console .log ('|   '.repeat (depth - 1)  + message)
  
function countup(n, depth = 1) {
  log(depth, `/ Calling with ${n}`)
  if (n < 1) {
    log(depth, `\\ Returning [] (base case)`)
    return [];
  } else {
    const countArray = countup(n - 1, depth + 1);  //the storing of 5,4,3,2,1 I don't understand
    log(depth, `| Pushing ${n} to [${countArray}]`)
    countArray.push(n); //I don't understand when countArray was defined as an array
    log(depth, `\\ Returning [${countArray}]`)
    return countArray;
  }
}

countup(5)

.as-console-wrapper {min-height: 100% !important; top: 0}

Answer 2

Every recursive function, that ends at least, will have a stop condition.

For your function that is

if (n < 1) {
 return [];
}

The other part of a recursive function is the actual recursion.

This happens here

const countArray = countup(n - 1);

You are calling the function with an n that is one less.

You'll hit that branch and trigger the recursion until you reach <1. At that point the array is created and it gets returned.

After that you get to push values in that array.

It is very important that you return countArray;, this way the array is pushed to the calling functions.

Most likely what you're missing is that when a function is called, the calling function waits for it to end and then goes further.

Usually you understand recursive functions if you try to map the stack and map all the calls to the functions.

Answer 3

(I know this should be a comment, but I can't add code in the comment section).

I think the best way to understand where the array is created, is following the flow yourself. It would make you understand better than all the words that an explanation could be made of.

Just do the following steps:

1. Open the console in your browser. Press F12 then click the console tab
2. Paste the code with a debugger statement:

-

function countup(n) {
  debugger;
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);  //the storing of 5,4,3,2,1 I don't understand
    countArray.push(n); //I don't understand when countArray was defined as an array
    return countArray;
  }
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

3. Use the step in and step over buttons
4. Have fun!

Answer 4

TL;DR

It is defined in return [];.

The parameter (n) decrements every time you enter the function and the array will be created if it reaches 0.

---

Let's say, you call countup(2).

This will reach the else that will call countup(1). That process repeats and calls countup(0).

This does not go in the else branch and instead creates and returns an empty array.

The calling method, countup(1) adds 1 to it (and returns the result) and it's caller countup(2) adds 2.

I will try to visualise the recursion:

countup(2)
  2<1 --> false --> else
  countArray=countup(1)
    1<1 --> false --> else
      countArray=countup(0)
        0<1 --> true --> if
        return []
      push 1 --> [1]
      return countArray --> [1]
  push 1 -->[1,2]
  return countArray -->[1,2]

Answer 5

At this point

const countArray = countup(n - 1);

the function "waits" and provokes a call to itself, which will stop only at the stop condition if (n < 1) at countup(0), which returns an empty array and returns to the preceding call of countup(1). At this point countArray gets the value returned from countup(0) which is [] and it is declared as an array, which also makes future push calls valid.

The variables are meanwhile stored in memory. When calling a function, it's parameters, along with it's local variables and return address are stored in the memory stack.

You might want to read more about recursion and call stack.