As a preface, it is difficult to speak about true fundamental limitations of things like abstract interpretation because "print Top" is a valid algorithm that will work for all programs. It is just completely useless. So you can model function calls in trivial ways (just treat calls and returns as giant phi nodes and widen whenever you hit mutual recursion). But this tends to produce pretty poor results for real programs and your fixed point computation tends to take longer due to the shape of real program call graphs. Add in dynamic dispatch and you've got all sorts of fun (watch all your pointers in a java program get merged through the receiver to Object.equals(), for example).

In practice, these structural differences require new approaches. The field has done a really good job at intraprocedural analysis, solving a lot of really important problems many decades ago. How to do fixed point computation over SSAed CFGs is well understood, even when you've got heap relationships to think about. Interprocedural analysis still largely sucks. Even modern approaches like CFL-reachability for dataflow analysis produce a ton of garbage. This is one reason why I say it is just harder.

As you mention, recursion prevents you from inlining everything into one giant function. You do get "the rest of the way there" by inlining to some depth limit in the sense that inlining is a way of achieving context sensitive analysis (though it is generally not preferred). But you've still got big problems at the points of mutual recursion (either you need to widen badly or you need to actually do interprocedural analysis) and your program is also exponentially larger in pathological cases.

Ahh I see! Thanks for the explanation.