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.

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.