One-Dimensional Array Iteration Using Recursion

Question

I'm trying to iterate over a simple array using recursion. For this specific case, I'm trying to recreate .map() using recursion (without using .map()!. I currently am only pushing the last element in the original array, but I want to push all into the array.

function recursiveMap (arr, func) {
 let newArr = [];
 if (arr.length === 1){
 newArr.push(func(arr));
 }
 else {
 newArr.push(...recursiveMap(arr.slice(1),func));
 }
 return newArr;
}

Answer 1

You need to to use func on the current item, and spread the result of calling the function on the rest of the array:

function recursiveMap(arr, func) {
 return arr.length ? [func(arr[0]), ...recursiveMap(arr.slice(1), func)] : [];
}
const arr = [1, 2, 3];
const result = recursiveMap(arr, n => n * 2);
console.log(result);

Answer 2

Your base case seems wrong. You will need to check for an empty array:

function recursiveMap (arr, func) {
 let newArr = [];
 if (arr.length === 0) {
 // do nothing
 } else {
 newArr.push(func(arr[0]));
 newArr.push(...recursiveMap(arr.slice(1),func));
 }
 return newArr;
}

Instead you will need to call func (on the first item) when there is at least one element.

Answer 3

With recursion, I find it is helpful to have the base case be the very first thing you check in your function, and short the execution there. The base case for map is if the array has 0 items, in which case you would return an empty array.

if you haven't seen it before let [a, ...b] is array destructuring and a becomes the first value with b holding the remaining array. You could do the same with slice.

function recursiveMap(arr, func){
 if(arr.length == 0) return [];
 let [first, ...rest] = arr;
 return [func(first)].concat(recursiveMap(rest, func));
}
let test = [1,2,3,4,5,6,7];
console.log(recursiveMap(test, (item) => item * 2));

EDIT

Going back to your sample I see you clearly have seen destructuring before xD, sorry. Leaving it in the answer for future readers of the answer though.

• Bergi: s/next/first/ :-)

Answer 4

Below are a few alternatives. Each recursiveMap

• does not mutate input
• produces a new array as output
• produces a valid result when an empty input is given, []
• uses a single pure, functional expression

---

Destructuring assignment

const identity = x =>
 x
const recursiveMap = (f = identity, [ x, ...xs ]) =>
 x === undefined
 ? []
 : [ f (x), ...recursiveMap (f, xs) ]
 
const square = (x = 0) =>
 x * x
 
console.log (recursiveMap (square, [ 1, 2, 3, 4, 5 ]))
// [ 1, 4, 9, 16, 25 ]

---

Array slice

const identity = x =>
 x
const recursiveMap = (f = identity, xs = []) =>
 xs.length === 0
 ? []
 : [ f (xs[0]), ...recursiveMap (f, xs.slice (1)) ]
 
const square = (x = 0) =>
 x * x
 
console.log (recursiveMap (square, [ 1, 2, 3, 4, 5 ]))
// [ 1, 4, 9, 16, 25 ]
 

---

Additional parameter with default assignment – creates fewer intermediate values

const identity = x =>
 x
const recursiveMap = (f = identity, xs = [], i = 0) =>
 i >= xs.length
 ? []
 : [ f (xs[i]) ] .concat (recursiveMap (f, xs, i + 1))
 
const square = (x = 0) =>
 x * x
 
console.log (recursiveMap (square, [ 1, 2, 3, 4, 5 ]))
// [ 1, 4, 9, 16, 25 ]

---

Tail recursive (and cute)

const identity = x =>
 x
 
const prepend = x => xs =>
 [ x ] .concat (xs)
 
const compose = (f, g) =>
 x => f (g (x))
const recursiveMap = (f = identity, [ x, ...xs ], then = identity) =>
 x === undefined
 ? then ([])
 : recursiveMap
 ( f
 , xs
 , compose (then, prepend (f (x)))
 )
const square = (x = 0) =>
 x * x
console.log (recursiveMap (square, [ 1, 2, 3, 4, 5 ]))
// [ 1, 4, 9, 16, 25 ]
// => undefined
recursiveMap (square, [ 1, 2, 3, 4, 5 ], console.log)
// [ 1, 4, 9, 16, 25 ]
// => undefined
recursiveMap (square, [ 1, 2, 3, 4, 5 ])
// => [ 1, 4, 9, 16, 25 ]

---

Derived from tail-recursive foldl – Note foldl chooses a similar technique used above: additional parameter with default assignment.

const identity = x =>
 x
const foldl = (f = identity, acc = null, xs = [], i = 0) =>
 i >= xs.length
 ? acc
 : foldl
 ( f
 , f (acc, xs[i])
 , xs
 , i + 1
 )
const recursiveMap = (f = identity, xs = []) =>
 foldl
 ( (acc, x) => acc .concat ([ f (x) ])
 , []
 , xs
 )
 
const square = (x = 0) =>
 x * x
 
console.log (recursiveMap (square, [ 1, 2, 3, 4, 5 ]))
// [ 1, 4, 9, 16, 25 ]

Answer 5

You could take another approach by using a third parameter for the collected values.

function recursiveMap(array, fn, result = []) {
 if (!array.length) {
 return result;
 }
 result.push(fn(array[0]));
 return recursiveMap(array.slice(1), fn, result);
}
console.log(recursiveMap([1, 2, 3, 4, 5], x => x << 1));
console.log(recursiveMap([], x => x << 1));

• Bergi: Talking about optimisations (especially tail calls that still isn't implemented) is kinda pointless when you still use array spread syntax on every step...
• Bergi: Also do you get into infinite recursion for an empty array?
• Nina Scholz: @Bergi, maybe it comes faster, than all users know this technique. anyway. it works now with an empty array as well.

Answer 6

welcome to Stack Overflow. You could either pass result to itself like in the following example:

function recursiveMap (arr, func,result=[]) {
 if (arr.length === 0){
 return result;
 }
 return recursiveMap(
 arr.slice(1),
 func,
 result.concat([func(arr[0])])
 );
}
console.log(recursiveMap([1,2,3,4],x=>(x===3)?['hello','world']:x+2));

Or define a recursive function in your function:

function recursiveMap (arr, func) {
 const recur = (arr, func,result=[])=>
 (arr.length === 0)
 ? result
 : recur(
 arr.slice(1),
 func,
 result.concat([func(arr[0])])
 );
 return recur(arr,func,[])
}
console.log(recursiveMap([1,2,3,4],x=>(x===3)?['hello','world']:x+2));

• Bergi: Using concat to append doesn't work when func returns an array
• HMR: @Bergi Yes, should use concat([value]) unless you're trying to flatten. I changed the code.

Answer 7

Add newArr.push(func(arr[0])); before calling again the function

function recursiveMap (arr, func) {
 let newArr = [];
 if (arr.length === 1){
 newArr.push(func(arr));
 }
 else {
 newArr.push(func(arr[0]));
 newArr.push(...recursiveMap(arr.slice(1),func));
 }
 return newArr;
}
console.log(recursiveMap([1,2,3], function(a){return +a+2}))

---

Same but modified answer with bugs corrected

function recursiveMap (arr, func) {
 let newArr = [];
 if(arr.length){
 newArr.push(func(arr[0]));
 if(arr.length > 1){
 newArr.push(...recursiveMap(arr.slice(1),func));
 }
 }
 return newArr;
}
console.log(recursiveMap([1,2,3], function(a){return a+2}))

• Bergi: This doesn't work on empty arrays. And does weird things on the last element - you really shouldn't need to use +a in your callback.
• Luis felipe De jesus Munoz: @Bergi Yes, I know but I didnt wanted to modified OP code, just give him the answer he was looking for so his understanding of the code didnt change.