Recursive vs iterative.

Or turning implicit into explicit.

Recursion is an extremely powerful and natural way of solving problems in terms of their simpler versions. Its declarative nature allows us to focus more on “what” instead of “how” and as such easier to understand and reason about. Famous interesting problems that are much easier to solve using recursion include a Sierpinski gasket

and Towers of Hanoi

as well as numerous algorithms like merge sort

The “magic” behind recursion is a stack which maintains execution context, so that we know how to proceed once we get a subproblem result

In fact, stack is so useful that CPUs even have dedicated instructions for performing common operations

Because of hardware support and a long history, we should expect recursion to be performant. So today, we are going to take a look at some trivial uses of recursion and how its performance compared to an iterative version.

Let’s start with a trivial single argument function

and benchmark their execution time using

And the results below show that the iterative version is almost 5 times faster than its recursive cousin.

Since our functions have just a single integer parameter, the only allocations used by exploreIter are those responsible for extending stack slice. What if we have 2 parameters wrapped into a struct? Let’s see

Technically we could avoid usage of params struct by using parallel arrays pattern but even with extra struct allocations

still suggest that iterative version is faster

These are arguably too abstract and not very useful functions, but being so simple they make it much easier to focus on recursive vs iterative aspect and in future posts we’ll take a look at more practical examples.