Number order in recursive arrays

JavaScript
1

I’m working on this challenge while trying to understand recursion. The challenge showcases this function:

function count(n) {
  if (n === 1) {
    return [1];
  } else {
    var numbers = count(n - 1); 
    numbers.push(n);
    return numbers;
  }
}

My most pressing question is why the array orders itself in ascending order, even when the value of n continues to decrease.

If one were to call the function count(10), it would return the array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. My understanding of the push() array method is that it pushes values to the end of the array.

If you step through the function, it would be as follows: n = 10, count is reduced, 10 gets pushed to numbers. n = 9, count is reduced, 9 gets pushed to numbers. Etc., until the end of the array. I can’t figure out why the number seems to be getting pushed to the beginning of the array and not the end.

2

Hello!

The simplest answer is because the count function starts filling the array when the if (n === 1) is executed, not before :stuck_out_tongue:. In other words, the first value of numbers is [1], then the n is just pushed to the array.

Look at the following topics:

If You still don’t understand I’ll try to explain it more.

1 Like
3

Take this with a grain of salt as I am still learning about recursive functions as well:

you asked about the order of the array and why the array output is [1,2,3...10] rather than [10, 9,8,...1]
from the computer’s perspective, it will not return anything until (n === 1) so what the computer does is it creates a ‘stack’ a stack of ‘pending’ material to eventually output.

Consider this analogy in explaining the code: a library wants to lend out n books (lets say 5 books) to its readers, however, the librarian will not distribute the 5 books until he has logged all these books into the library archive to verify they have a record of them in the library. The librarian takes the pile of books 5 tall, all of them not logged to the library records. He takes the top one (the 5th book if we count 1-5, bottom to top) and logs it. There are still 4 more books he must log prior to checking the books out. Therefore, the librarian creates a ‘stack’ of pending books to check out, this first book in the ‘stack’ is read as ‘n = 5’ in our code. He then takes from the unchecked pile of books the 4th to the top book (the new top), logs it, and puts it on the ‘stack’ pile, this book is n = 4, then the unchecked pile book 3 is removed, logged, set upon the ‘stack’ then the unchecked pile book 2, logs it, places upon the ‘stack’ and finally he reaches the bottom of the unchecked books, n===1 finally and once that book is logged, he puts it on top of the ‘stack’ of books which now reads n=5 on bottom, 4, 3, 2, n=1 on top. The librarian can take the n=1 book, and check it out to a reader which in code is displayed [1] then the n=2 book goes out, the array reads [1,2], etc until the final book n=5 that was on the bottom of the stack goes out, [1,2,3,4,5] the library has a log of all the books it checked out.

function count(n) {
  if (n === 1) {
    return [1];
  } else {
    var numbers = count(n - 1); 
    numbers.push(n);
    return numbers;
  }
}

(for a visual step by step logic completion of JS code, this tool will be useful: http://pythontutor.com/javascript.html#mode=edit)

3 Likes
4

First of all, you don’t really need else after return, so you can write your function like so:

function count(n) {
  if (n === 1) return [1]; // line 1
  var numbers = count(n - 1); // line 2
  numbers.push(n); // line 3
  return numbers; // line 4
}

Now watch what will happen if I swap lines 2 and 3, and try to see why it’s happening

function count(n) {
  if (n === 1) return [1]; // line 1
  var numbers = [n]; // line 2, same as var numbers = []; numbers.push(n);
  numbers = numbers.concat(count(n - 1)); // line 3
  return numbers; // line 4
}
1 Like
5

These helped a lot, thank you. I think I understand how the code is working now!

6

Just to add, this is a kinda complicated way of doing things. It’s easier to just build up a list clearly rather than doing the little dance you do with push in this function. And in languages where you use recursion a lot, and you’re building lists, you normally reverse the result once you’ve unwound the stack (or use a reverse append function that reverses the list as you iterate), because generally lists are linked lists and it is much faster to append to the start of a list than it is to calculate length and add to the end every iteration. eg in JS (although not necessary, just as an example):

function count (n, current = 1, output = []) {
  if (current > n) {
    return output.reverse();
  } else {
    return count(n, current + 1, [current, ...output]);
  }
}

But as arrays in JS are not linked lists, there isn’t a performance penalty to appending to the end so can just do like:

function count (n, current = 1, output = []) {
  if (current > n) {
    return output;
  } else {
    return count(n, current + 1, output.concat(current));
  }
}

For comparison, Elixir:

defmodule Counter do
  @moduledoc """
  Produce a range of numbers from 1 to a given positive integer inclusive.

      iex> Counter.count(10)
      [1,2,3,4,5,6,7,8,9,10]

      iex> Counter.count(0)
      []
  """

  # Function head definition to, include default 
  # params to allow the function to be called
  # with only `n`
  def count(n, current \\ 1, output \\ [])
  # Terminal case, counter value has passed the input number, return reversed output
  def count(n, current, output) when n > current, do: Enum.reverse(output)
  # Recursive case, push the current counter value into
  # the output array and increment the counter
  def count(n, current, output), do: count(n, current + 1, [current|output])
end

ReasonML:

let count = (n) => {
  let rec loop = (current, output) =>
    (current > n)
  	? List.rev(output)
  	: loop(current + 1, [current, ...output])

  loop(1, [])
}

EJ1RIS1WwAAbSg3