CODEWITHSUNDEEP
javascriptarraysrecursion
Erin Fleming
Erin Fleming

Reputation: 27

Javascript unshift(), recursion and making an array

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

I found the above code in freeCodeCamp. I ran it on VS code. It works, but I don't understand how. Here is my question: How can you unshift() onto a variable that has not yet been declared as an array such as []? It just says that const arr = countdown(n-1). It does not say that const arr is an array such as "[]". If I try to unshift() integers onto a variable that has been declared as just "arr" without any "[]", it runs as an error. However, in this code that I found on freeCodeCamp, it works. Why?

Upvotes: 0

Views: 115

Answers (3)

Mulan
Mulan

Reputation: 135397

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]

Upvotes: 3

Will Ness
Will Ness

Reputation: 71119

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.

Upvotes: 1

BossCode
BossCode

Reputation: 71

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.

Upvotes: 0

Related Questions