Javascript unshift(), recursion and making an array

substitution

If I say x = 5 and then ask "What is x + 3?". Without much help one can answer, 8. When you are asked how you arrived at your answer, you explain that you substituted x with its value, five, and then added plus three.

If given a function f(x) = 3 * x + 2 or max(a,b) = a > b ? a : b, I can ask you other questions like what is f(4) or max(9,7)? And you'll arrive at the answer the same way:

• What is f(4)?
  • What is f? → f is x -> 3 * x + 2
  • What is x? → x is 4
  • What is 3 * 4 + 2?
    • What is 3 * 4? → The answer is 12
    • What is 12 + 2? → The answer is 14
    • The answer is 14
  • The answer is 14
• The answer is 14

• What is max(9,7)?
  • What is max? → max is (a,b) => a > b ? a : b
  • What are a and b? → a is 9 and b is 7
  • What is 9 > 7 ? 9 : 7?
    • What is 9 > 7? → The answer is true
    • What is true ? 9 : 7? → The answer is 9
    • The answer is 9
  • The answer is 9
• The answer is 9

And so with a recursive function, we can use substitution to answer these questions

• What is countdown(5)?
  • What is countdown?
    • countdown is

      function countdown(n) {
        if (n < 1) {
          return [];
        } else {
          const arr = countdown(n - 1);
          arr.unshift(n);
          return arr;
        }
      }
      

  • What is n? → n is 5
  • What is ...?

    if (5 < 1) {
      return [];
    } else {
      const arr = countdown(5 - 1);
      arr.unshift(5);
      return arr;
    }
    

    • What is 5 < 1. → The answer is false
    • What is ...?

      if (false) {
        return [];
      } else {
        const arr = countdown(5 - 1);
        arr.unshift(5);
        return arr;
      }
      

      • The answer is

        const arr = countdown(5 - 1);
        arr.unshift(5);
        return arr;
        

      • What is arr?
        • The answer is countdown(5 - 1)
        • What is 5 - 1? → The answer is 4
        • What is countdown(4)?

so what is arr?

Using substitution to compute countdown(5) leads us to compute countdown(4), where again we can use substitution. countdown(4) will look almost exactly the same as before, and as you continue on with countdown(3) and countdown(2) we notice the n - 1 pattern play out. Until finally n = 0 and the conditional n < 1 is now true...

• What is countdown(0)?
  • The answer is []

We can use substitution all the way -

• What is countdown(3)?
  • What is arr?
  • arr is countdown(3 - 1)
  • What is countdown(2)?
    • What is arr?
    • arr is countdown(2 - 1)
    • What is countdown(1)?
      • What is arr?
      • arr is countdown(1 - 1)
      • What is countdown(0)?
        • The answer is []
      • arr is []
      • What is arr.unshift(1)? → * The answer is [1]
      • The answer is [1]
    • arr is [1]
    • What is arr.unshift(2)? → The answer is [2,1]
    • The answer is [2,1]
  • arr is [2,1]
  • What is arr.unshift(3)? → The answer is [3,2,1]
  • The answer is [3,2,1]
• The answer is [3,2,1]

one caveat

Recursion is a functional heritage and so using it with functional discipline yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects. Above we can use substitution because countdown has referential transparency. That's a fancy way to say that the function always returns the same result if the same inputs were given. In functional discipline you always design functions in this way, so your programs can be assembled and combined, like formulas in an evolving system of equations.

there is no arr

JavaScript has strong support for functional style and so our programs can be written with rich expressions. Program semantics are undisturbed by intermediate assignments like arr and syntax boilerplate like if, else, return, and {...} lying about.

const countdown = n =>
  n < 1
    ? []
    : [ n, ...countdown(n - 1) ]
    
console.log(countdown(5))

[5,4,3,2,1]

According to its definition, the function countdown satisfies the equations

.....
countdown(-2) = []
countdown(-1) = []
countdown(0) = []
countdown(1) = { const arr = countdown(0);
                 arr.unshift(1);
                 return arr;  }
             = countdown(0).unshift(1);        // countdown(0)=[]
             = [].unshift(1);
             = [1]
countdown(2) = countdown(1).unshift(2);        // countdown(1)=[1]
             = [1].unshift(2);
             = [2,1]
countdown(3) = countdown(2).unshift(3);        // countdown(2)=[2,1]
             = [2,1].unshift(3);
             = [3,2,1]
.....

so actually everything is defined quite alright.

This works because arr is actually declared as an array. This is because when arr is declared it is declared as the output of countdown(n -1). Since countdown has an exit condition that returns a new array [] which will eventually be reached because n is decreasing every time its called. This is a basic example of recursion, a goog way to find out how it works is to step through the code in you mind or a debugger.