Not Sure Why This Function Returns A Reversed Array

August 21, 2024 Post a Comment

I'm working on a JavaScript exercise and having some trouble untangling the logic as to why it works. It basically has a function called 'mystery' that uses a bunch of very simple

Solution 1:

mystery is a recursive function.

It calls itself using the return value of the rest function, which returns everything except the first element.

It uses the result of that + the result of first, which returns the first character, and concatenates them again (using conj), but with the first element at the end.

So, say you put in [H e l l o],

it will return conj(mystery([e l l o], H)

mystery([e l l o]) will return conj(mystery([l l o], e)

mystery([l l o]) will return conj(mystery([l o], l)

and so on, until the array that goes into mistery is empty, in which case the recursion ends, and we bubble back up to the first call.

Side note, recursion is often used for exercises like this, but although it has some specific uses, in many cases it's way more efficient to not use recursion, because the overhead of making another function call is relatively hard work, compared to other solutions using a simple loop to move or swap items around.

You can see what is happening if you output some information:

functionrest(arr) {
  return arr.slice(1);
}


functionfirst(arr) {
  return arr[0];
}

functionconj(arr, value) {
  arr.push(value);
  return arr;
}

functionmystery(array, level) {
  if (array.length === 0) {
    console.log('mystery level '+level+' is called with an empty array. Recursion ends here.. Stay tuned for the answer.');
    return [];
  }
  console.log('mystery level '+level+' is called with '+array+
              '. I will move '+first(array)+' to the end.');
  
  var result = conj(mystery(rest(array), level+1), first(array));
  console.log('returning '+result+' for level '+level);
  return result;
}

console.log(mystery(['H','e','l','l','o'], 0));

Solution 2:

To understand a function that uses recursion it can help to just assume for a moment that the recursive (nested) call returns what it should and then see how it builds on that to produce a correct result.

Let's for example suppose that array is [1, 2, 3, 4]

So this line:

conj(mystery(rest(array)), first(array));

... has a recursive call of mystery. It gets as argument the array, but with the first element removed from it (that is what rest returns), so it gets [2, 3, 4]

Now we will just assume that this recursive call of mystery does the right thing and reverses that array into [4, 3, 2]. Then in the above quoted code we see this result is concatenated with first(array) (which is the first value, i.e. 1). So we get [4, 3, 2, 1]. Correct!

This teaches us that if we assume mystery does the job right for an array with n-1 values, it also does it right for n values.

Now remains to see whether mystery deals correctly with the smallest case, i.e. when the array is empty. It is easy to see it returns the correct result in that case, i.e. an empty array.

So putting those two things together you can see that mystery does the job correctly for all possible array sizes.

Solution 3:

your first function "rest" removes the first element, as slice will return elements from 1 to the end of the array, then the "conj" function will take the first element that was removed (through the "first" function) and put it in the end, and doing so recursively it'll take elements from the beginning and put them to the end.

Solution 4:

The .push method places the item to end of array. .slice(1) means “except the first item”

Pseudocode

Get array A (arg of mystery). If it is empty, return it
Take rest (everything except the first). We will call the rest B
Run this program on B (recursively)
Append the first item of A to end of B

conj = append value to arr

first = get first item of arr

rest = return everything except the first item

mystery when array is empty = return empty array

mystery when array is not empty = Take rest(array), run mystery on it, then append first of array

Solution 5:

Yeah, the magic of recursion. To understand think about what it does if you call mystery with a 2-element array [1,2].

rest(array) will then be [2]mystery(rest(array)) will also be [2]

first(array) will be 1.

Then you return conj([2], 1) which locically results in [2,1].

Now the trick is the recursion. If you have 3 elements [0,1,2] and call mystery with it this will happen:

it will call mystery(rest(array)) with essentially is mystery([1,2]). That this returns [2,1] have we already seen.
first(array) will be 0
so it returns conj([2,1],0) which is logically [2,1,0].

this now recusivly works for as many elements as you wish. Essentially mystery will be called for every element to place it after all elements.

JavaScript File