I want to write a recursive function in javascript that returns an array with its elements reversed. This code generates the following error:

undefined is not a function

function reverseArray (toBeReversed){
  var reversed = [];

  function reverser (toBeReversed){
    if (toBeReversed.length == 1)
      reversed.push(toBeReversed[0]);
    else {
      reversed.push(toBeReversed.lastOfIndex(0)); //error on this line
      reverser(toBeReversed.slice(-1));
    }
  }

  reverser(toBeReversed);
  return reversed;
}

I want to write a recursive function in javascript that returns an array with its elements reversed. This code generates the following error:

undefined is not a function

function reverseArray (toBeReversed){
  var reversed = [];

  function reverser (toBeReversed){
    if (toBeReversed.length == 1)
      reversed.push(toBeReversed[0]);
    else {
      reversed.push(toBeReversed.lastOfIndex(0)); //error on this line
      reverser(toBeReversed.slice(-1));
    }
  }

  reverser(toBeReversed);
  return reversed;
}

• javascript
• arrays
• recursion

• Any reason for not using the revers() function that javascript already has? – sparrow Commented Jan 18, 2015 at 0:57
• 2 What is your question? Also read this. Also how is it that a subarray of length one 1. needs to be reversed 2. needs to be reversed later – philipxy Commented Jan 18, 2015 at 1:06
• Wow, these comments and answers. You have a typo. lastOfIndex instead of lastIndexOf I'm not sure what these other users are smoking. (Your code doesn't work though) – david Commented Jan 18, 2015 at 2:56
• 2 Well I'm smoking the 'lets try to help the newbie learn recursion' pipe, rather than just fix the typos in the not-really-working code... :) – Barney Commented Jan 18, 2015 at 3:02
• Let's all smoke that pipe :). Seriously though, all of this help is appreciated. I need to get into the programmer state of mind... – guptam Commented Jan 19, 2015 at 2:53

11 Answers 11

A classic recursive implementation would be

function reverse(a) {
    if (!a.length) return a;
     return reverse(a.slice(1)).concat(a[0]);
}

You don't need any loops, or arrays accumulating values, or functions inside functions, or any other machinery.

If you prefer writing little one-liners to make your code more readable, then

function head(a)    { return a[0];         }
function tail(a)    { return a.slice(1);   }
function push(a, v) { a.push(v); return a; }
function empty(a)   { return !a.length;    }

function reverse(a) { 
    if (empty(a)) return a;
    return push(reverse(tail(a)), head(a)); 
}

This little program has the property that it can be "read" as English, which I think more programs should have. In this case it's

The reverse of an array is (1) empty, if it is empty; (2) otherwise, the result of adding the head to the end of the reverse of the tail.

Unfortunately, even in JS implementations which provide optimized tail recursion (precisely none at this point in time), it will not be applied in this case, since JS has to keep the stack around to call concat on the result of reverse each time around. Can we write something that is optimizable? Yes, by carrying around another value, namely the result of reversing the array so far:

function unshift(a, v) { a.unshift(v); return a; }

function reverse(a) { return _reverse(a, []); }

function _reverse(a, result) {
    if (empty(a)) return result;
    return _reverse(tail(a), unshift(result, head(a)));
}

Or if you prefer

function reverse(a) { 
    return function _reverse(a, result {
        if (empty(a)) return result;
        return _reverse(tail(a), unshift(result, head(a)));
    }(a, []);
}

This is not quite as clean, but gives us the benefit of being able to still think recursively, without the normal stack overhead associated with recursion.

lastOfIndex is not a function, you probably mean to use lastIndexOf. here is a similar way:

function reverseArray (toBeReversed){
  var reversed = [];

  function reverser (toBeReversed){
    if (toBeReversed.length !== 0){
      reversed.push( toBeReversed.pop() );
      reverser( toBeReversed );
    }
  }

  reverser(toBeReversed);
  return reversed;
}

const recursiveRev = arr => arr.length === 0 || arr.length === 1 ? arr : arr.slice(arr.length-1).concat(recursiveRev(arr.slice(-arr.length, -1)));

I came up with this answer by using recursion

function reverse(arr) {
    return (arr.length > 1) ? [arr.pop()].concat(reverse(arr)) : arr.pop();
}

const dataSet = [0, 1, 2, 3, 4];

console.log(reverse(dataSet));

This keeps being resurrected, but there rarely seems to be any improvement on this answer. However in modern JS, there is a nicer syntax for that algorithm:

const reverse = ([x, ...xs]) =>
  x == undefined ? [] : [... reverse (xs), x]

console .log (reverse ([9, 0, 3, 5, 7, 6, 8]))

This is how I would approach it:

function reverse(arr) {
  var result = [];
  var count = arr.length;

  function recur() {
     if (result.length < arr.length) {
       result.push(arr[--count]);
       return recur();
     } else {
       return result;
     }
  }

  return recur();
}

Usage:

var letters = ["a", "b", "c", "d", "e", "f", "g", "h"];
var reversed = reverse(letters);

Output:

console.log(reversed);
//=> ["h", "g", "f", "e", "d", "c", "b", "a"]

// Original array is unmodified
console.log(letters);
//=> ["a", "b", "c", "d", "e", "f", "g", "h"]

Try

function reverseArray (arr) {
  return (function reverser(r, t) {
    r.push(t.splice(-1, 1)[0]);
    return !!t.length ? reverser(r, t) : r
  }([], arr));
};

function reverseArray (toBeReversed) {
  return (function reverser(r, t) {
r.push(t.splice(-1, 1)[0]);
return !!t.length ? reverser(r, t) : r
  }([], toBeReversed));
};

var rev = document.getElementsByTagName("pre")[0];
document.getElementsByTagName("button")[0]
.addEventListener("click", function(e) {
  rev.innerText = "[" + reverseArray(JSON.parse(rev.innerText)) + "]"
})

<pre>[1,2,3,4,5,6,7]</pre><button>click</button>

Here is my solution which manipulates the original array.

   function reverseArr(arr, i, j){
      if(i < j){
        var temp1 = arr[i];
        arr[i] = arr[j];
        arr[j] = temp1;
        i++;
        j--;
        return reverseArr(arr,i,j);
      } else if(i === j ){
        return arr;
      }
    }
    var originalArr = [1,5,7,3,2,9,11];
    result = reverseArr(originalArr, 0, originalArr.length-1);
    console.log(result);

Link to fiddle: https://jsfiddle.net/octopuscode/opyes4nd/2/

let arr = ["1","2","3"]; //declaration of array

function reverseArr(param){
  let i=param.length; //set counter i to the array length
  
  if(i==0){ //when to exit recursion
    return;
  }
  
  console.log(param[i-1]) //what to do until you exit,[i-1] because arrays are 0-based
  param.pop(param[i-1]) //pop already printed element from array
  
  reverseArr(param) //pass the new array and invoke function again
}

reverseArr(arr)

Simple implementation of a very simple algorithm using recursion -

I/P : ["h" , "e", "l", "l" , "o"] O/P: [ "o" , "l", "l", "e", "h" ]

Idea:

If I can somehow take out the first element and put it in the last index my job is done.

Explanation :

Since, we are using recursion we can have the first element of the array stored in the stack.

Now, we know stack work on LIFO. So, going by the above principle if my last element of the array goes in the stack at first and if we can push the last element in an empty array first, then we can achieve the output.

Algorithm:

1. Pop the first element of the array
2. Call the same function until all the elements have been popped and the array is empty.
3. Push the last element that has been popped in the empty array.

Code:

    function reverseArray (s) {
    if(s.length === 0) { // base case of the recursion
        return []
    }

    let v = s.shift(); // Pop out the first element
    reverseArray(s); // repeat the operation for the next element
    s.push(v); // Once base case is reached start pushing the last popped element in the array
    return s;
}


console.log(reverseArray(["h" , "e", "l", "l" , "o"]))

Note: If you are not clear how recursion works, what's call stack etc. you might want to read "Thinking Recursively" - by Eric Roberts.

Here is my solution for a reverse function that is:

• Deep.
• Does not alter the input array.

The main idea is to check for arrays-within-arrays and reverse those inner arrays too (See arr2 and arr3).

First, we initialize reversed, which will be our final output array. Next, we start from the last element in our input array and iterate backwards, while checking each element using isArray():

• If an element IS NOT an array, then we simply add it to reversed.
• If an element IS an array, then we recursively call our function with this element as the input (and go 1 level deeper!).

Just like any recursion problem, the return values eventually "bubble up" to the top. To see the whole picture, I find it easiest to simply go through one of the examples.

const reverser = (array) => {
  const reversed = [];
  for (let i = array.length-1; i >= 0; i-- ) {
    if (Array.isArray(array[i])) {
      reversed.push(reverser(array[i]))
    } else {
      reversed.push(array[i])
    }
  }
  return reversed;
}

const arr1 = [1,2,3,4,5,6,7,8,9]
const arr2 = [[1,2,3],[4,5,6],[7,8,9]]
const arr3 = [[[1,2],[3]],[[4,5],[6]],[[7,8],[9]]]

console.log(reverser(arr1))
console.log(reverser(arr2))
console.log(reverser(arr3))