Home

30 November 2019

Performance of recursion versus iteration in javascript: An Interactive analysis

Recursions are functions that call themselves directly or indirectly. Iteration is the process where a set of instructions or statements are executed repeatedly for a specified number of time or until a condition is met.

We are already familiar with both methods, the discussion here is about the performance in the browser implementations. Here we will consider the time complexity and space complexity.

Let us check the performance here. We will run a classic function of finding the power of a number, our inputs are base and exponent. We expect the answer as base exponent . See the code below and run the function to get an analysis.


function powerByRecursion(base, exponent) {
  if (exponent === 0) {
    return 1
  } else {
    return base * powerByRecursion(base, exponent - 1)
  }
}
    

function powerByIteration(base, exponent) {
  let result = 1
  for (let i = 0; i < exponent; i++) {
    result *= base
  }
  return result
}
  
    

Time Complexity

Lets see how the time complexity of the recursion method.

      
  # time complexity of recursive method
  T(n) = { T(n-1) + 1 when n > 0, 1 when n = 0}

  T(n) = T(n-1) + 1
  T(n-1) = T(n-2) + 1
  T(n-2) = T(n-3) + 1
  ...
        
  therefore, T(n) = T(n-k) + k
  we know that
      T(0) = 1
  consider, T(n-k) = 1
  So, n-k=0
      n = k     
  therefore T(n) = 1 + n
  So the time complexity is O(n)     
      
    

The time complexity of iteration is similar O(n), since there are n times for running through the loop.

Space Complexity

Lets see how the space complexity of the recursion method.

To compute the space complexity of recursion we need to understand how the stack frames are generated in memory. When fn1 is called from fn2 stack frame corresponding to this function 'fn1' is created. This stack frame is kept in the memory until call to function 'fn1' is not terminated. This stack frame is responsible for saving the parameters of function 'fn1', local variables in the function 'fn1' and return address of caller function(function 'f0'). Now when this function 'fn1' calls another function 'fn2', stack frame corresponding to 'fn2' is also generated and is kept in the memory until call to 'fn2' is not terminated.

Behind the hood we know javascript is single threaded and the heap memory is storing the state of each function call. This makes us question the efficiency of recursion in terms of space. All browsers keep a limit to the heap memory size so obviously we will hit the stackoverflow error when the heap is full. Thus the space complexity of recursion is O(n)

Iteration on the other hand executes and discards the resources used in the previous loop. In our case the space complexity is O(1).

Running tests

Here we will run the functions one by one and profile the time taken in each case by using the window.performance.now() browser api and get an analysis. The space taken is not possible to calculate but we can hit the limit by putting huge numbers in the exponent

base= exponent=

Method Start Time End Time Time taken
Results
Recursion
Iteration

Did you see iteration is faster? Well thats not a surprise.

There is an optimization mechanism called Tail Call optimization. Only Safari implements it and the proposal for making a more universal solution is inactive https://github.com/tc39/proposal-ptc-syntax/issues/22#issuecomment-319099634.

If you have tried enough times you can reach the limits of your stack in Recursion method

If you see recursion is faster, there are a few points to consider here.

Conclusion

While running a recursive function in js we cannot expect to get a result because of the Max call stack reached error. So we can do it the iterative way. Speed of running is almost same and we can be pretty happy with that.

I have added here the whole mechanism under the hood of this particular test I have done. Feel free to check it out.

      
function runTests() {
  // get the values of base and exponent from the input tag as integers
  const base = parseInt(document.getElementById('base').value,10)
  const exponent = parseInt(document.getElementById('exponent').value,10)
  let recursionErrored = false
  // when a string is parsed it will be NaN so checking if the inputs are numbers
  if (base && typeof base === 'number' && exponent && typeof exponent === 'number') {
    // The performance.now() method returns a DOMHighResTimeStamp, 
    // measured in milliseconds with precision to microseconds
    // But in firefox microseconds is disabled by default
    // https://developer.mozilla.org/en-US/docs/Web/API/Performance/now
    document.getElementById('status').textContent = 'Starting tests...Dont panic if browser freezes :P'
    // resetting existing values in table
    document.getElementById('recursion-start').textContent = ''
    document.getElementById('recursion-end').textContent = ''
    document.getElementById('recursion-value').textContent = ''
    document.getElementById('recursion-time').textContent = ''
    document.getElementById('iteration-start').textContent = ''
    document.getElementById('iteration-end').textContent = ''
    document.getElementById('iteration-value').textContent = ''
    document.getElementById('iteration-time').textContent = ''
    document.getElementById('difference').textContent = ''
    document.getElementById('result').textContent = ''
    setTimeout(() => {
      let startTimeOfRecursion = window.performance.now()
      document.getElementById('recursion-start').textContent = startTimeOfRecursion
      let recursionValue = 'Max call stack exceeded'
      try {
        recursionValue = powerByRecursion(base, exponent)
      } catch (err) {
        console.log(err);
        recursionErrored = true
      }
      let endTimeOfRecursion = window.performance.now();
      document.getElementById('recursion-end').textContent = endTimeOfRecursion
      let recursionTime = (endTimeOfRecursion - startTimeOfRecursion)
      document.getElementById('recursion-time').textContent = recursionTime + 'ms'
      document.getElementById('recursion-value').textContent = recursionValue
      let startTimeOfIteration = window.performance.now()
      document.getElementById('iteration-start').textContent = startTimeOfIteration
      const iterationValue = powerByIteration(base, exponent)
      let endTimeOfIteration = window.performance.now()
      document.getElementById('iteration-end').textContent = endTimeOfIteration
      let iterationTime = (endTimeOfIteration - startTimeOfIteration)
      document.getElementById('iteration-time').textContent = iterationTime + 'ms'
      document.getElementById('iteration-value').textContent = iterationValue
      const difference = Math.abs(recursionTime - iterationTime)
      document.getElementById('difference').textContent = 'Δ ' + difference + 'ms'

      document.getElementById('status').textContent = 'Tests completed'
      if (recursionErrored) {
        document.getElementById('result').textContent = 'Since maximum call stack reached for recursion. We dont have a comparison here'
      } else {
        document.getElementById('result').textContent = (recursionTime < iterationTime ?
          'Recursion'
          : 'Iteration') + ' is faster by '
          + Math.round(difference / Math.max(iterationTime, recursionTime) * 100) + '%'
      }
    }, 100)
  }
}
      
      

Thanks