Way of understanding recursion properly (javascript)

Question

I'm trying to understand recursion and I have a somewhat decent understanding on how it intuitively works, however the aggregation of the returned data is the bit I struggle with.

For instance, in javascript to flatten an array I came up with the following code:

var _flatten = function(arr){
    if(!arr instanceof Array) return arr;
    var g = [];

   function flatten(arr){

     for(var i = 0; i < arr.length;i++){
         if(arr[i] instanceof Array){
         flatten(arr[i]);
         }else{
         g.push(arr[i]);
        }
     }
   }

  flatten(arr);
  return g;
}

Turning something like this

var list = [1,2,3,4,5,6,[1,2,3,4,5,[1,2,3],[1,2,3,4]]];

into this:[ 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 4 ]

Which is fine and all, but the global variable g seems like some kind of cheap hack. I don't know how to think about the result returned when getting to the top of the stack and the return of the function propagating back down the stack. How would you implement this function, and how can I get a better grasp on this?

Thanks!

Answer 1

Instead of a global variable (to make it more proper recursion) you can send in g as a argument to the flatten function, and pass the modified g back out with a return statement.

var _flatten = function(arr) {
  if (!arr instanceof Array) return arr;

  function flatten(arr, g) {
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] instanceof Array) {
        flatten(arr[i], g);
      } else {
        g.push(arr[i]);
      }
    }
    return g;
  }

  return flatten(arr, []);
}

Answer 2

In fact recursive coding is very simple and every aspects of it shall be contained in the function body. Any info that needs to pass shall be sent through arguments to the next recursion. Usage of global thingies is very ugly and shall be avoided. Accordingly i would simply do the in place array flattening job as follows;

var list = [1,2,3,4,5,6,[1,2,3,4,5,[1,2,3],[1,2,[9,8,7],3,4]]];

function flatArray(arr){
  for (var i = 0, len = arr.length; i < len; i++)
    Array.isArray(arr[i]) && (arr.splice(i,0,...flatArray(arr.splice(i,1)[0])), len = arr.length);
  return arr;
}

console.log(flatArray(list));

Answer 3

There are many ways to write an array flattening procedure but I understand your question is about understanding recursion in general

The g isn't global in any sense of the word, but it is a symptom of the implementation choices. Mutation isn't necessarily bad so long as you keep it localized to your function – that g is never leaked outside of the function where someone could potentially observe the side effects.

Personally tho, I think it's better to break your problem into small generic procedures that make it much easier to describe your code.

You'll note that we don't have to setup temporary variables like g or handle incrementing array iterators like i – we don't even have to look at the .length property of the array. Not having to think about these things make it really nice to write our program in a declarative way.

// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = f => xs => xs.map(f).reduce((x,y) => x.concat(y), [])

// id :: a -> a
const id = x => x

// flatten :: [[a]] -> [a]
const flatten = concatMap (id)

// isArray :: a -> Bool
const isArray = Array.isArray

// deepFlatten :: [[a]] -> [a]
const deepFlatten = concatMap (x => isArray(x) ? deepFlatten(x) : x)

// your sample data
let data = [0, [1, [2, [3, [4, 5], 6]]], [7, [8]], 9]

console.log(deepFlatten(data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

console.log(flatten(data))
// [ 0, 1, [ 2, [ 3, [ 4, 5 ], 6 ] ], 7, [ 8 ], 9 ]

First you'll see I made two different flattening procedures. flatten to flatten one level of nesting, and deepFlatten to flatten an arbitrarily deep array.

You'll also see I use Array.prototype.map and Array.prototype.reduce since these are provided by ECMAScript but that doesn't mean you're only limited to using procedures that you have. You can make your own procedures to fill the gaps. Here we made concatMap which is a useful generic provided by other languages such as Haskell.

Utilizing these generics, you can see that deepFlatten is an insanely simple procedure.

// deepFlatten :: [[a]] -> [a]
const deepFlatten = concatMap (x => isArray(x) ? deepFlatten(x) : x)

It's made up of a single expression including a lambda made up of a single if branch (by use of the ternary operator ?:)

---

Maybe it's a lot to take in, but hopefully it demonstrates that "writing a recursive procedure" isn't always about complicated setup of state variables and complex logic to control the recursion. In this case, it's a simple

if (condition) recurse else don't

If you have any questions, let me know. I'm happy to help you in any way I can.