Odtnhj

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 functions, and returns an array you give it but in reversed order. I've been sitting in front of a whiteboard for an hour trying to figure out the logic behind it, and not getting it. Can a kind soul take a look at these functions and explain how the mystery function returns a reversed array? Thank you!

function rest(arr) 
 return arr.slice(1);



function first(arr) 
 return arr[0];


function conj(arr, value) 
 arr.push(value);
 return arr;


function mystery(array) 
 if (array.length === 0) 
 return ;
 
 return conj(mystery(rest(array)), first(array));

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.

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:

function rest(arr) 
 return arr.slice(1);



function first(arr) 
 return arr[0];


function conj(arr, value) 
 arr.push(value);
 return arr;


function mystery(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));

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.

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

Pseudocode

1. Get array A (arg of mystery). If it is empty, return it


2. Take rest (everything except the first). We will call the rest B


3. Run this program on B (recursively)


4. 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

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.

One thing to note here is that mystery() is called recursively. I added some comments to illustrate what's going on on each step.

function rest(arr) 
 console.log('take first n-1 elements of', arr);
 return arr.slice(1);



function first(arr) 
 return arr[0];


function conj(arr, value) 
 arr.push(value);
 console.log('combine', arr, 'with', value)
 return arr;


function mystery(array) 
 console.log('call mystery on ', array)
 if (array.length === 0) 
 return ;
 
 return conj(mystery(rest(array)), first(array));


mystery([0,1,2])

It's pretty simple. The reason for you not being able to see it is RECURSION. Couple things, that I would like you to notice:

• mystery(array) is recursive function because it call itself until the array passed in is emplty


• all of your work is happening here: return conj(mystery(rest(array)), first(array));
  

I'm not going to talk more about recursive function here rather I will show how you can track each recursive call using console.log(). Check out my code below, I've added console.log() to make things more clear for you. Try running mystery with some array and see results. This will make sense to you.

function rest(arr) 
 return arr.slice(1);



function first(arr) 
 console.log("Returning ",arr[0], "from first(arr).")
 return arr[0];


function conj(arr, value) 
 console.log("Pushing ",value, " to ",arr, " in conj(arr,value)");
 arr.push(value);
 console.log("Returning ",arr, " from Conj(arr,value)");
 return arr;


function mystery(array) 
 if (array.length === 0) 
 console.log("array is emplty. So, returning empty array from mystery");
 return ;
 
 console.log("array is not emplty. So, calling mystery(array) again.");
 return conj(mystery(rest(array)), first(array));

var reverse =mystery([1,2,3,4]);
console.log("The final result", reverse);

Not gonna lie, this is a weird way to reverse the order of the array. It's basically using recursion to slice the first element of the array and conjoin the elements with first element at the end.

So here's a walk though:

mystery(['h','e','l','l','o']) ->

first check if array is empty then method rest is called ->

rest(['h','e','l','l','o']) ->

rest slices the array at index 1 returning a new array of ['e','l','l','o'] ->

then mystery is called which repeats the previous steps with the return value of rest ->

mystery(['e','l','l','o']) ->

this means the mystery will be keep getting called on until rest returns an empty array ->

mystery(['e','l','l','o']) ->
mystery(['l','l','o']) ->
mystery(['l','o']) ->
mystery(['o']) ->
mystery() ->

when mystery has an empty array it returns the empty array and then first is called ->

first returns just the first element of the array and happens after mystery is returned it would look something like this before mystery is returned ->

mystery(['e','l','l','o']) , first(['h','e','l','l','o']) ->

so at the lowest level when mystery returns an empty array and first return the first element in ['o'] it would look like this ->

, ['o'] ->
conj would be called with these values ->
conj( , ['o']) ->
conj returns the combination of the two values ->
conj( , ['o']) ->
['o'] ->

this is then returned and repeated ->
conj( , ['o']) ->
conj(['o'] , ['l']) ->
conj(['o','l'] , ['l']) ->
conj(['o', 'l','l'] , ['e']) ->
conj(['o', 'l','l', 'e'] , ['h']) ->
['o', 'l','l', 'e','h']