implementing a recursive reverse function in javascript

Question

I'm trying to write a function that reverses a list. The function is recursive.

I know javascript does not have TCO, but i wanted to experiment with this anyway:

reverse = function(list) {
 if (list.length < 2) { return list }
 fk = fork(list);
 return reverse(fk.tail).concat([fk.head])
}

the fork function splits a list to a head and a tail:

fork = function(list) {return {head: list[0], tail: list.slice(1)}}

When I call reverse() with the list [1,2,3,4,5], I get this result:

reverse([1,2,3,4,5]) // [5,4,4,4,4]

Not sure what I'm doing wrong here. The expected result is [5,4,3,2,1].

Please help.

• adeneo: You know this is already built in natively as Array.reverse
• dopatraman: I know this, but i wanted to build it myself in scholarly interest.

Answer 1

You should lint your code, that'll help you tremendously. In particular, this code fails because fk is treated as a global variable. If you prefix it with var, it works:

var reverse = function(list) {
 if (list.length < 2) { return list }
 var fk = fork(list);
 return reverse(fk.tail).concat([fk.head])
}

As it stands now, at each recursive call you modify the same fk variable, essentially meaning concating the same fk.head - the element before the last one.

---

In fact, you don't even need temporary variable here:

function recursive_reverse(list) {
 return list.length < 2 ? list : recursive_reverse(list.slice(1)).concat([list[0]]);
}

---

As for tail recursion, here's one possible approach:

function recursive_reverse(list) {
 return tail_recursive_reverse(list, []);
}
function tail_recursive_reverse(list, res) {
 if (!list.length) return res;
 var head = list[0];
 var tail = list.slice(1);
 res.unshift(head);
 return tail_recursive_reverse(tail, res);
}

• dopatraman: this line return tail_recursive_reverse(tail, (res.unshift(head), res)); calls the tail recursive function with 3 arguments instead of two. Did you mean for the last two to be in an array?
• raina77ow: No, it's two arguments there; the second one is the result of comma expression (that is its second operand - res). Parentheses are for a reason there. )
• dopatraman: What is the need for the comma expression?
• raina77ow: res.unshift(head) returns a new length of an array, not an array itself. But in this case, one wants res to be passed further. Of course, it's not necessary, one can just write res.unshift(head) as a standalone expression. I've rewritten, as it seems to cause a confusion.
• dopatraman: interesting... i didnt know one could do that. thanks for the explanation.