# How are (mutually) recursive methods inferred correctly?
**URL:** https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463
**Category:** Internals & Design
**Tags:** recursion
**Created:** [July 10, 2023, 11:58pm UTC](https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463 "2023-07-10T23:58:10Z")
**Posts on this page:** 4
**Page:** 1
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [July 10, 2023, 11:58pm UTC](https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463/1 "2023-07-10T23:58:10Z")
This is something I took for granted and never really thought of. A C example I pulled from wikipedia will help me explain:
```julia
# 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}`.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [July 11, 2023, 5:01am UTC](https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463/2 "2023-07-11T05:01:37Z")
Stumbled upon a JuliaHub blogpost [Inference Convergence Algorithm in Julia](https://info.juliahub.com/inference-convergence-algorithm-in-julia) link in the devdocs section [How inference works](https://docs.julialang.org/en/v1/devdocs/inference/#How-inference-works) that answers the question to my satisfaction, though I do not know if it is entirely up to date.
---
### Author:  [@Sevi](https://discourse.julialang.org/u/Sevi)
#### Post date: [July 11, 2023, 6:36am UTC](https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463/3 "2023-07-11T06:36:41Z")
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!
---
### Author:  [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [July 11, 2023, 7:02am UTC](https://discourse.julialang.org/t/how-are-mutually-recursive-methods-inferred-correctly/101463/4 "2023-07-11T07:02:20Z")
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.