The Problem with Recursion

I remember the exact moment recursion broke my brain: my second year of university.

Erlang was the language they picked for the concurrent programming module.

I’d never seen a functional language before. The first thing I noticed was the thing that wasn’t there: no loops. No for. No while. Nothing.

One of my first assignments was to implement Fibonacci. I sat there with my notebook open, drawing little decision trees. Base case. Recursive case. Base case. Recursive case.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).

I followed the pattern like a mantra:

Write the base case.
Write the recursive case.
Hope it terminates.

I had no intuition for it. I just copied the shape… but then it clicked (eventually).

The idea that a function could call itself and that was the whole mechanism.

No loop counter. No mutable state. Just functions calling functions.

I felt enlightened. Like I’d been handed a secret.

I started writing recursion everywhere. I wrote a recursively descending tree traversal in JavaScript that blew up the stack and crashed the browser tab. That brought me back to reality.

Recursion is cool. It’s powerful. It’s genuinely cute… a function calling itself! And it works!

But it’s also unreadable. Unless the recursion is dead simple and obviously appropriate for the use case, I’m too dumb to read it without sitting down and cosplaying a turing machine.

Recursion, As Intended

I’m not saying never write recursion. There are places where it’s the correct tool.

But they’re rarer than people think.

A GenServer loop is recursive by nature: handle_call calls itself through the return value and that’s fine. The recursion is the architecture.

Binary pattern matching sometimes genuinely benefits from recursion.

Parsing a binary protocol where each chunk determines how to parse the next chunk.

defp parse_chunks(<<size::32, data::binary-size(size), rest::binary>>, acc) do
  parse_chunks(rest, [data | acc])
end

defp parse_chunks(<<>>, acc) do
  Enum.reverse(acc)
end

This is… fine. It’s readable.

It’s a simple accumulate-and-reverse pattern. You can see the base case and the recursive case without squinting.

But even here, you could do this with Stream.unfold or Enum.reduce_while.

Recursion isn’t wrong, it just makes you go “huh??” during a code review because it’s unexpected, and that’s a red flag. It stands out. It makes you think “wait, did I miss something?”

There’s nothing wrong with a good ol’ fashioned Enum.reduce. Everyone knows what it does.

Recursion is also sometimes a sign that something should be a GenServer.

Or a GenStateMachine… which can be scary if you’re not familiar with them, but they’re at least explicitly scary.

A recursive function masquerading as a pure helper is implicitly scary. I’d rather be scared on purpose.

Not Invented Here

The problem with recursion isn’t that it’s wrong.

It’s that it’s unnecessarily complex. Other APIs exist. They’re faster, better tested, and everyone knows what they do.

Writing your own recursion is just being clever for no reason.

Here’s a real function from a production codebase. It works. It’s recursive. And it should not exist.

(I actually found it while looking for examples for this post… and I went “huh??” when I read it).

defp compare_entries(%{datetime: t1} = e1, %{datetime: t2} = e2) do
  case DateTime.compare(t1, t2) do
    :lt -> true
    :gt -> false
    :eq ->
      if e1.transaction_type == e2.transaction_type &&
           e1.transaction_id == e2.transaction_id do
        compare_entries(
          %{debit: e1.debit_cents, credit: e1.credit_cents, acc: e1.account},
          %{debit: e2.debit_cents, credit: e2.credit_cents, acc: e2.account}
        )
      else
        if e1.transaction_type == e2.transaction_type do
          e1.transaction_id < e2.transaction_id
        else
          e1.transaction_type < e2.transaction_type
        end
      end
  end
end

defp compare_entries(%{debit: 0, credit: eq, acc: a1}, %{debit: 0, credit: eq, acc: a2}) do
  a1 < a2
end

defp compare_entries(%{debit: 0, credit: c1}, %{debit: 0, credit: c2}) do
  c1 > c2
end

defp compare_entries(%{debit: eq, acc: a1}, %{debit: eq, acc: a2}) do
  a1 < a2
end

defp compare_entries(%{debit: 0}, %{debit: _}) do
  false
end

defp compare_entries(%{debit: _}, %{debit: 0}) do
  true
end

defp compare_entries(%{debit: d1}, %{debit: d2}) do
  d1 > d2
end

Eight clause heads. Two different arities. Self-recursion between arities with completely different map shapes. A hand-rolled multi-level sort comparator.

Lemme walk you through what makes this so bad…..

It’s a State Machine

The first clause takes structs with datetime, transaction_type, and transaction_id.

When the datetimes are equal and the transaction IDs match, it constructs brand maps with a different shape: %{debit: ..., credit: ..., acc: ...}.

Then it calls itself with a different arity…

Those clauses that don’t pattern match a datetime can only be reached through this self-recursive path. They have no callers anywhere else in the codebase.

The function is a hidden state machine but you have to simulate the whole thing in your head to understand what it does.

Implicit Ordering

The second family of clauses compares debit amounts, credit amounts, and account IDs. But the ordering matters.

Swap any two and the behavior silently changes.

Some clauses are mirrors of each other:

(%{debit: 0}, %{debit: _}) returns false.
(%{debit: _}, %{debit: 0}) returns true.

These exist purely to handle edge cases the developer couldn’t express as a simpler rule.

Mic Drop

This entire function is a sort comparator.

It’s deciding which of two entries comes first based on datetime, then transaction type, then transaction ID, then debit, credit, and account.

That’s a multi-field sort key. And Elixir has a built-in way to do that.

Enum.sort_by(entries, &{
  &1.datetime,
  &1.transaction_type,
  &1.transaction_id,
  &1.debit_cents,
  &1.credit_cents,
  &1.account
})

One line.

The standard library is better than your recursion in every way that matters.

You can assume it’s relatively optimal. Everyone knows what it does. It’s battle tested.

You writing it yourself is just being clever for no reason.

If your recursion looks like a fold, it’s Enum.reduce. If it looks like a map, it’s Enum.map. If it looks like a sort, it’s Enum.sort_by.

Please :’)