JavaScript - Recursion vs Iteration

Story time: recently I had to solve a problem and wanted to impress by doing it in the most elegant way possible. That being said, I spent some hours writing a recursive algorithm with the smallest possible complexity but in the end, I sent an iterative approach in O(n^2). After submitting my solution, I got curious to know how JavaScript handles recursion vs iteration and then this post came to life.

In general terms, recursion and iteration do the same things: they solve a task a piece at time. The difference is that while iteration repeats a task until it’s complete, recursion breaks it into small tasks until there’s a solution.

There’s no consensus on which approach is more efficient. To illustrate, see two implementations of Fibonacci’s Sequence algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function recursiveFibonacci(n) {
	if (n <= 1) {
		return n;
	}
	else {
		return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
	}
}
function iterativeFibonacci(n) {
	int x = 0, y = 1, z = 1;
	for (int i = 0; i < n; i++) {
		x = y;
		y = z;
		z = x + y;
	}
	return x;
}

The first approach (recursive one), although it’s small, has a complexity of O(2^n), while the second approach (iterative one) has complexity of O(n). That is, one is exponential and the other is linear, with significant impacts on their execution times.

Right not you probably asking yourself “if there’s this huge difference between the two, why there’s any doubt on which one to choose?”. The point is that there are problems where a recursive approach is more ideal, for example when we are dealing with ADTs (abstract data types), such as:

1
2
3
4
5
6
7
8

function walkDOM(node, func) {
	func(node);
	node = node.firstChild;
	while(node) {
		walkDOM(node, func);
		node = node.nextSibling;
 	}
}

The above function easily allow us to walk through DOM nodes and apply a function to each one of them.

Complexity and running times aside, a very common problem in recursive algorithms are infinite calls, for example a factorial algorithm where N < 0. That is, when working with recursive approaches, you must always ensure the existence of a base-casis that will eventually happen.

If there’s a possibility for your algorithm to have an infinite number of calls or even a big number of them, you’ll face a problem known as Stack Overflow, where the stack‘s size exceeds its own limits causing a crash in your software.

One of the ways to avoid Stack Overflow in very “deep” calls is a resource called tail call optimization, this resource allows you to do calls without growing the stack size, EcmaScript adopted it on v6.

1
2
3
4
5
6
7
8
9
10

function factorial(n) {
	if (!n) return 1;
	return n * factorial(n-1);
}
function factorialTCO(n, partialFactorial = 1) {
  if (!n)
      return partialFactorial;
  return factorialTCO(n - 1, n * partialFactorial);
}

The first approach does not fit tail call optimization given it returns the value of n and the result from the recursive call. Meanwhile, the second approach fits because only the function return value is returned.

After those informations, the only possible conclusion is that there’s not silver bullet way of writing algorithms, it solely relies on the implementation and needs of your project, after all front-end performance is way more than algorithms and their time complexities.