# How are (mutually) recursive methods inferred correctly?

This is something I took for granted and never really thought of. A C example I pulled from wikipedia will help me explain:

``````# really inefficient check of evenness or oddness
# "is n even" -> "is n-1 odd" -> "is n-2 even", repeat to 0
is_even(n) = iszero(n) ? true : is_odd(n-1);
is_odd(n) = iszero(n) ? false : is_even(n-1);
``````

When I usually explain Julia’s JAOT compilation, I say that when a function is called `is_even(0x8)`, the compiler infers the call’s possible return types from the input types `(UInt8,)`, and the result depends on inferring the return types of other function calls `is_odd(0x7)` along the way, one call at a time. However, I can’t explain how inference completes when `is_even` depends on the return type of `is_odd` which depends on the yet-to-be-inferred `is_even`. Now I think about it, I can’t explain how 1 recursive function can be inferred.

Even if I replace `true` with `rand((true, 1))` in `is_even`, the `code_warntype` shows that both return types of `is_even` and `is_odd` are inferred as `Union{Bool, Int64}`.

2 Likes

Stumbled upon a JuliaHub blogpost Inference Convergence Algorithm in Julia link in the devdocs section How inference works that answers the question to my satisfaction, though I do not know if it is entirely up to date.

2 Likes

This is a question I didn’t even know I had

We don’t know what we don’t know…

Thanks for the links – very interesting!

Since tail recursions, mutual or not, can be trivially rewritten as loops, the type inference result from any reasonable algorithm should be the same as the type inference result for loop-based code.

2 Likes