Understanding recursion using iteration (or vice versa)

Introduction

Understanding how recursion works can be difficult. In this lesson, we're going to look at how to flatten an array using iteration. Afterwards, I will write down a recursive solution to compare this too.

The Stack

The power of recursion is the stack. Each time a function calls itself, all variables are re-initialized. If you want to share state between function calls, you can either pass them along each function call explicitly, or you can use a closure to encapsulate data structures you want access through to all calls. There are pros and cons to each here.

The approach we'll use here is to simulate encapsulation, meaning our state stack will not need to pass along the resulting output array to each iteration.

The Approach

Here is an overview of our approach:

We're going to use a depth-first iterative method to flatten an array. The idea is to add each non-array item to a result array. When an array is discovered, we do some bookkeeping to remember where we left off then start analyzing this sub-array. Repeat.

How To Do It

Keep a results array and a state stack to track two states,

1. an array to analyze and analyze
2. a location in that array to start analyzing start

We'll want to start by setting the initial state of the stack, called stack

1. The array will be the base array
2. The index will be the zeroth index

So everything in our while loop is driven off of these states, start of type number and analyze of type array<unknown>

Now, while we have states in our stack stack

1. Iterate this array until a sub-array is discovered; otherwise, add the value to the result array
2. When a sub-array is discovered
   • Remember our current state
   • Set up the next state, the sub-array and index zero

Once we no longer have states, return the result.

The Code

// O(N)
function flattenArrIter( arr ) {
  // edge case, array is empty 
  if(!arr.length) return arr

  // output array
  let result = []
  // track states, start with first item in
  // given array
  let stack = [{ start:0, analyze: arr }]
  // while we have states in the stack
  while( stack.length ) {
    // destructure the states
    let { start, analyze } = stack.pop()
    let index = start
    // iterate until an array is discovered or we run out of items in the array
    while( index < analyze.length && !Array.isArray( analyze[index] ) ) {
      result.push( analyze[index] )
      index++
    }
    // if we have items in the array, we know that we must have found
    // an embedded sub-array
    if( index < analyze.length ) {
      // remember to start with the next item in the array after
      // analyzing the sub array
      stack.push({ start:index + 1, analyze })
      // start analyzing the sub array
      stack.push({ start:0, analyze: analyze[index] })
    }
  }
  // no more items in the stack
  return result
}

The Recursive Ways

Now let's look at the recursive way of doing this. First up, we'll use encapsulation.

function flattenArrWithEncapsulation( arr ) {
  // encapsulation, our helper will have access
  // to result array across function calls
  let result = []
  helper( arr )
  return result 

  function helper( analyze ) {
    for( let index = 0; index < analyze.length; index++ ) {
      let item = analyze[index]
      if( Array.isArray(item) ) {
        helper( item ) 
      } else {
        result.push( item )
      }
    }
  }
}

This function is pure because while it does mutate internally, it is deterministic and mutates nothing externally.

Also, its important to realize that while the function itself is pure, the inner helper function is not pure. It is bound to this function and mutates values outside itself. In this case the result array is mutated.

This is a good function to study when comparing recursion to iteration, at least for this particular case. Notice how each recursive call will spawn a new values for index and analyze just like the iterative method. This is how we "utilize the recursive stack"!

Side note:

Because we can use the for-of syntax here, we can re-write this in a more elegant way

function flattenArrWithEncapsulation( arr ) {
  // encapsulation, our helper will have access
  // to result array across function calls
  let result = []
  helper( arr )
  return result 

  function helper( analyze ) {
    for( let item of analyze ) {
      if( Array.isArray(item) ) {
        helper( item ) 
      } else {
        result.push( item )
      }
    }
  }
}

This masks how recursion is keeping track of the index in this stack. I thought to include it here to provide an additional point of comparison.

Bonus: Other Ways To Solve Recursively

In case you're wondering about encapsulation and mutation, let's consider how we could re-write using no encapsulation

function flattenArrNoEncapsulationNotPure( arr, result = [] ) {
  for( let item of arr ) {
    if( Array.isArray(item) ) {
      flattenArrNoEncapsulationNotPure( item, result ) 
    } else {
      result.push( item )
    }
  }
  return result
}

Neat! Yet this function is not pure! It mutates result!

Let's see how we can write this with no encapsulation and no mutation

// Don't use this, very inefficient! ~ greater than O(N^3) time complexity!
function flattenArrNoMutationNoEncapsulation( arr, index = 0, result = [] ) {
  // base case
  if( arr.length === index) {
    return result
  }
  if( Array.isArray( arr[index] ) ) {
    return result.concat( flattenArrNoMutationNoEncapsulation( arr[index], 0, result) )
  } else {

    return result.concat( arr[index] ).concat( flattenArrNoMutationNoEncapsulation( arr, index + 1, result) )
  } 
}

OK, I don't recommend using this, because it is much MUCH slower than all the other functions here. In fact, it will not run in O(N) time! This is because each concat call run in linear time, unlike push which is a constant time O(1) operation.

I believe the time complexity grows in Squared Pyramidal time

https://en.wikipedia.org/wiki/Square_pyramidal_number

Conclusion

In this article we looked at how to manually keep a state stack to emulate recursive solutions using iteration. These kinds of exercise help in understanding what the "recursive stack" is. I hope this has been a useful introduction in how iteration and recursion relate to each other.