Home

30 November 2019

** 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**. 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 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)
```

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).

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.

- Are you using firefox browser? Here the performance is calculated by the

`window.performance.now();`

web api.
performance.now()
reference
To offer protection against timing attacks and fingerprinting, the precision of performance.now() might get rounded depending on browser settings. In Firefox, the privacy.reduceTimerPrecision preference is enabled by default and defaults to 1ms.

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)
}
}
```

- Chinchuna Pavithran for proof reading and complexity analysis