Can You Invert a Recursive Function?

A function is invertible if and only if it is injective: distinct inputs produce distinct outputs.

Recursion is an implementation. It does not decide invertibility. The combining step at each recursive call does.

The two examples below share the same recursive shape and differ only in that step.

1 Invertibility

Given \(f\), ask whether two distinct inputs can share an output.

If yes: no inverse exists. The output does not determine the input.
If no: \(f\) is injective. An inverse may be written on the image of \(f\).

Inspect what each recursive step keeps or discards.

2 Invertible case: binary digits

to_binary converts a non-negative integer to bits. Each step records \(n \bmod 2\) and recurses on \(n // 2\). The base case \(n = 0\) returns [].

from_binary walks the same structure in reverse.

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)

Each step keeps the bit it produced plus a smaller instance of the same problem. The base case [] is not confusable with a partial result.

On its actual image — bit lists with no trailing zero — to_binary is a bijection. from_binary on a list outside that image returns a number with no matching to_binary preimage.

3 Non-invertible case: summation

total has the same shape: take the first item, combine with the recursive result on the rest, stop at []. The combining operator is addition.

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 calls return 6.

Each step keeps only the running sum. Position and identity of the summands are discarded. That step is a lossy accumulator: many-to-one.

Consequences:

Distinct inputs share an output, so total is not injective.
No inverse exists.

Any recursive function whose combining step is many-to-one is in the same class.

4 Speculation: memory as an accumulator

This section is not a result about minds.

If perception and memory fold each moment into a running gist and discard order and detail, they have the same shape as total. A non-injective encoding is irreversible: later reconstruction cannot recover what the combining step did not keep.