## DEV Community

YCM Jason

Posted on • Updated on

# The problem

Given any list `xs`, where `xs` could contain other lists or any non-list values, we wish to extract all the values in `xs`. For example:

1. `flatten([1, [3], [[6, 7], [[[]], 8]]]) => [1, 3, 6, 7, 8]`
2. `flatten([{a: 3}, 1, [[''], 2]]) => [{a: 3}, 1, '', 2]`

# Recursive solution

When we wish to derive a recursive solution, we must avoid thinking recursively. Never trace your code into the recursive calls! The correct approach is to assume that the function you want to define is already working on a smaller structure of the input, which in this case the smaller structure is obviously the tail of `xs`, i.e. `xs.slice(1)`. This assumption is called `the leap of faith`.

So now if `flatten(xs.slice(1))` will work correctly, how could we use this to construct the full correct answer of `flatten(xs)`? Now obviously we are missing `xs[0]`. `xs[0]` could either be a non-list element or another list.

If `xs[0]` is a non-list element, we simply add back `xs[0]` to the first place of `flatten(xs.slice(1))`, then we are done!

If `xs[0]` is another list, we take a `leap of faith` and recursively call `flatten(xs[0])`. Then we can concat `flatten(xs[0])` to `flatten(xs.slice(1))`.

``````function flatten(xs){
if(Array.isArray(xs[0])) return [...flatten(xs[0]), ...flatten(xs.slice(1))];
else return [xs[0], ...flatten(xs.slice(1))];
}
``````

Now what we miss is a base case. The smallest list that we can flatten must be `[]`, and the answer is obviously `[]`.

So the final code is

``````function flatten(xs){
if(xs.length === 0) return [];

if(Array.isArray(xs[0])) return [...flatten(xs[0]), ...flatten(xs.slice(1))];
else return [xs[0], ...flatten(xs.slice(1))];
}
``````

Marko Taponen

In order to understand recursion one must understand recursion.

YCM Jason

my favourite quote of all time!

Sebastian Rapetti • Edited

Hi!
PHP do not have native functions for flatten.
gist.github.com/s3b4stian/0e2e638a...

Maroun Baydoun • Edited

What do you think about my solution? Flatten an array in JavaScript

YCM Jason • Edited

1. checking array should be done with `Array.isArray()` (here)
2. I think it would be better if you take the base case outside your `reducer` function.
If I were going to define `flatten` with reduce, I would have written something like the following:
``````function flatten(xs){