Struggling to understand how this code works

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

I can understand why once it gets to the Array.push that it prints out [1], but after that I don't understand how it goes from [1] to [1,2,3,4,5].

Also, wouldn't (n-1) always have to be 1-1 as without it the if (n < 1) won't be true?

CodePudding user response：

It should all become clear if you step through it line by line in a debugger:

I wasn't able to record it as slowly as I would have liked to, because I was running into some max. sizes for creating a GIF from it. It's probably best if you do the same yourself anyway. Watch the call stack and the values of the local variables. When you do this interactively, I'd encourage you to also explore the local variables of the higher-up instances of your function in the call stack (you can click on a call stack entry to switch to its scope).

1. countup(5) is called, so n = 5. Since 5 is not less than 1, we go to the else branch. With n = 5, we get n - 1 = 4 so countup(4) is called.
2. Same as #1, but with n = 4, eventually calling countup(3).
3. Same as #1/#2 several more times until we end up calling countup(0). At this point we have a total of 6 instances of the function in the call stack.
4. With n = 0, we enter the first branch of the if, returning an empty array [].
5. The countup(1) instance receives the return value of [] from countup(0) and stores it into countArray.
6. The countup(1) instance pushes n (1) into countArray, yielding [1]. The array is then returned to the called (countup(2)).
7. The countup(2) instance receives the return value of [1] from countup(1) and stores it into its own countArray.
8. The countup(2) instance pushes n (2) into countArray, yielding [1, 2]. The array is then returned to the caller (countup(3)).
9. Steps #5-8 continue for countup(3), countup(4) and countup(5), until at the end countup(5) pushes 5 into its countArray, ending up with [1, 2, 3, 4, 5], and that array is now returned to the caller (the main function).
10. The main function got the result [1, 2, 3, 4, 5] from countup(5) which is now passed into console.log.

You can also think about it like this:

• countup(0) returns []¹.
• countup(n) for any nonzero n returns [...countup(n - 1), n]².

(...where ...array means the spread operator so [a, ...[b, c], d] becomes [a, b, c, d])

So we get the following evolution:

Upwards:

countup(0) = []
              \_______________________
                                      \
countup(1) = [...countup(0), 1] = [...[], 1] = [1]
                                         ______/
                                        /
countup(2) = [...countup(1), 2] = [...[1], 2] = [1, 2]
                                            ____/
                                           /
countup(3) = [...countup(2), 3] = [...[1, 2], 3] = [1, 2, 3]
                                               ____/
                                              /
countup(4) = [...countup(3), 4] = [...[1, 2, 3], 4] = [1, 2, 3, 4]
                                                  ____/
                                                 /
countup(5) = [...countup(4), 5] = [...[1, 2, 3, 4], 5] = [1, 2, 3, 4, 5]

Downwards:

countup(5) = [...countup(4),  5]
              |············\__ \__
              |···············\   \
           = [...countup(3),  4,  5]
              |············\__ \__ \__
              |···············\   \   \
           = [...countup(2),  3,  4,  5]
              |············\__ \__ \__ \__
              |···············\   \   \   \
           = [...countup(1),  2,  3,  4,  5]
              |············\__ \__ \__ \__ \__
              |···············\   \   \   \   \
           = [...countup(0),  1,  2,  3,  4,  5]
              |··· _______/   |   |   |   |   |
              |···/           |   |   |   |   |
           = [...[],          1,  2,  3,  4,  5]
              \_x_/           |   |   |   |   |
           = [                1,  2,  3,  4,  5]

_{1: Technically, any n < 1 would make countup(n) return [], not only n = 0.}

_{2: Technically, the same array is used all the time here and just mutated in every step. In a pure functional way of handling this, a copy would have to be created (const countup = n => n < 1 ? [] : [...countup(n - 1), n]). But that doesn't matter for this explanation because the array is of course no longer needed in the previous function after it was returned.}

CodePudding user response：

Adding some logging should help you understand the execution sequence. This is triggered initially with countup(5), which then recursively calls countup(n-1) until n-1 is 0. That returns an empty array, and then each previous call of countup appends n to the array and returns it. So you end up with an execution order like:

countup(5)
calls countup(4)
calls countup(3)
calls countup(2)
calls countup(1)
calls countup(0), which returns [] to countup(1)
the call from countup(1) appends 1 to the (empty) array and returns [1] to countup(2)
the call from countup(2) appends 2 to the array and returns [1, 2] to countup(3)
the call from countup(3) appends 3 to the array and returns [1, 2, 3] to countup(3)
the call from countup(4) appends 4 to the array and returns [1, 2, 3, 4] to countup(4)
the call from countup(5) appends 5 to the array and returns [1, 2, 3, 4, 5]

function countup(n) {
  console.log('countup(' n ')');
  if (n < 1) {
    console.log('returning empty array');
    return [];
  } else {
    console.log('calling countup - 1');
    const countArray = countup(n - 1);
    console.log('pushing ' n);
    countArray.push(n);
    console.log('returning countArray:');
    console.log(countArray);
    return countArray;
  }
}

console.log(countup(5));

CodePudding user response：

Recursive approaches are interesting but kind of difficult to understand at first glance. In this particular example, the function evaluates for a very specific constraint. If n < 1 the function will return an empty Array. Let's dive into the code execution:

• On the first iteration n = 5 that allow the else block to be executed. Once the second countup call (countup(n - 1)) it evaluates the input again, and since n is still greater than 0 the whole process will repeat itself.
• Once the countup function receives an input of 0 (n = 0) it returns an empty array. Such array is then assigned to the countArray variable (in this particular point countArray = []) and the current value of n is pushed into the array (since the n = 0 case already returned, you'll land on the case where n=1). Again this process will repeat itself in every step up until you reach the case where n=5 (technically your first iteration). Once 5 has been pushed into the array, the function will return the array containing every value from 1 to the provided number n sorted from the smallest to the largest number.

CodePudding user response：

If n = 0, it will return an empty array,. If n = 1, the function countup will call itself with n-1 returing and empty array, and after that will push n on the empty array returning [1]. If n = 2, the function countup will call itselft with n-1, as you can immage, n-1 in this case is 1, so the function countup will return [1], and then push n on the array, so the result will be [1, 2] and so with any positive number.