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.

You know this is already built in natively as Array.reverse — adeneo
– adeneo, Commented Feb 3, 2016 at 17:37
I know this, but i wanted to build it myself in scholarly interest. — dopatraman
– dopatraman, Commented Feb 3, 2016 at 17:42

raina77ow · Accepted Answer · 2016-02-03 18:24:13Z

5

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);
}

edited Feb 3, 2016 at 18:24

answered Feb 3, 2016 at 17:38

raina77ow

107k16 gold badges205 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

dopatraman Over a year ago

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 Over a year ago

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 Over a year ago

What is the need for the comma expression?

raina77ow Over a year ago

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 Over a year ago

interesting... i didnt know one could do that. thanks for the explanation.

Collectives™ on Stack Overflow

implementing a recursive reverse function in javascript

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related