I think the C preprocessor is an interesting example of (2), because the metaprogramming community has converged on an extremely clever paradigm to circumvent the lack of recursion: continuation machines. By defining a linear number of “continuation evaluation” macros, you can generate an exponential number of “recursive” macro expansions, which trivially scales to the point that it could take until the heat death of a universe for an arbitrary program to terminate, but a program can choose to terminate at any time. The Chaos-pp and Order-pp projects are good implementations of this!