Can You Invert a Recursive Function?

Recursion and reversibility are unrelated questions

It’s tempting to think a recursive function is somehow “reversible by nature” — it peels a problem down to a base case, so surely you can walk back up. You can’t, not automatically. Whether a function can be undone has nothing to do with how it’s defined and everything to do with whether it’s injective: does every distinct input land on a distinct output? If two different inputs can produce the same output, no amount of cleverness recovers which one you started from. The recursion is just the implementation; injectivity is the property that decides the question.

The invertible case: turning a number into bits and back

to_binary peels the least-significant bit off n at each step and recurses on what’s left:

Code

def to_binary(n: int) -> list[int]:
    if n == 0:
        return []
    return [n % 2] + to_binary(n // 2)


def from_binary(bits: list[int]) -> int:
    if not bits:
        return 0
    return bits[0] + 2 * from_binary(bits[1:])


to_binary(13), from_binary(to_binary(13)), from_binary(to_binary(13)) == 13

([1, 0, 1, 1], 13, True)

It inverts cleanly because every recursive step keeps exactly the information needed to undo itself: the bit it just produced, plus a smaller version of the same problem. Nothing is merged or thrown away, and the base case ([], meaning “done”) is never confusable with an in-progress result. Rebuild bit by bit, in reverse order, and you’re back where you started — the recursion is a bijection wearing a function’s clothing.

The lossy case: summing a list

total looks structurally identical — recurse, combine, done — but combine here means add, and addition forgets:

Code

def total(xs: list[int]) -> int:
    if not xs:
        return 0
    return xs[0] + total(xs[1:])


total([1, 2, 3]), total([3, 2, 1]), total([6])

(6, 6, 6)

All three return 6. total is a lossy accumulator: each step folds one element into a running scalar and discards the element’s identity — its position, its neighbors, everything but its contribution to the sum. Three different lists collapse onto one number, so no inverse function can exist; there’s no fact of the matter about which list “the” 6 came from. This isn’t a bug or a missing feature — it’s forced by the shape of the recursion itself, the moment the combining step is many-to-one.

A speculative closing thought

It’s hard not to notice that a lot of lived experience looks like total, not to_binary. Perception and memory don’t archive raw frames — they fold each moment into a running impression, a mood, a gist, discarding the order and detail the way total discards which numbers summed to 6. Ask someone how their week was and you get a scalar, not a list.

Maybe that’s a small, non-mystical reason experience feels irreversible: not because time itself refuses to run backward, but because the encoding we use to hold onto it is non-injective by construction — much like a sum. You can’t invert total([1, 2, 3]) any more than you can rerun Tuesday from how it left you feeling. The information needed to undo it was never kept in the first place.