Letrec requires either laziness (which implies some sort of internal mutability, as thunks get replaced by values at some point), or "internal" mutability that may not be visible to the programmer (like in OCaml, where in a `let rec` some variables will initially be null pointers, and get updated once other definitions have run).
In languages with no mutability at all (not even internal mutability like with these two features), you can't create cycles and refcounting becomes possible, but I'm not aware of non-academic general purpose languages that actually fall in this category.
Esoteric functional languages like Unlambda do make that guarantee, and implementations can use a ref counter as their GC.
If data is immutable and you tie the lifetime of data to a single stack frame, you only need a single bit for reference counting: whether the current frame owns the reference. Calling a function just requires setting this to bit low (some asterisks here), and all objects tied to a given frame can be collected when the frame returns.
Erlang does have some mutability (the process dictionary, and the mailbox), but the fact that the language is largely immutable is leveraged by the GC: if I remember correctly the private heap GC is a generational semi-space copying GC, but because the language is immutable it doesn’t need to have write barriers, to perform a minor collection only a scan of the stack（and process dict) is necessary to know the valid roots of the young heap.
In languages with no mutability at all (not even internal mutability like with these two features), you can't create cycles and refcounting becomes possible, but I'm not aware of non-academic general purpose languages that actually fall in this category.
Esoteric functional languages like Unlambda do make that guarantee, and implementations can use a ref counter as their GC.
I've written more about this here: https://terbium.io/2019/09/cyclic-immutable/