How do compilers work in a language that doesn't allow recursion?

Question

I'm recently learning the programming language, and I wonder how compilers work when the language itself does not allow recursion, like how the compiler or the runtime checkers makes sure that there is no recursion. I learned that compilers don't need to understand recursion when translating the code, but how does one work without understanding it? I try to think to allocate a specific size of stack to avoid recursion, but then I think I have no idea about how to determine the size.
I assume that it is not the language don't have recursion feature but the compilers or checkers don't allow.

Answer 1

Recursion can only be programmed either by having a call to function A within the definition of A itself (direct), or by having function A call function B, and function B call function A (indirect). It is easy to forbid both possibilities simply by requiring that every call to a function must occur after the definition of that method is complete.

The technical term is forward referencing; every recursive program must contain at last one syntactical forward reference. By forbidding the forward reference, you implicitly also disallow any recursion.

Answer 2

To support recursion, a language needs to support function calls and a call stack. When a language doesn't allow recursion, it's typically because the language lacks one of these features. I'm not aware of any mainstream language which do have a call stack but nevertheless disallows recursion.

For example, earlier versions of BASIC did not have function calls, so there was no way to implement recursion. Some processors and associated assembly languages don't support recursion either, because the processor has no built-in call stack.

Early versions of FORTRAN did support function calls, but they could only store a single return address per function. They didn't have a call stack. So if a function called itself it would never exit again.

Languages in the ML family (like F#) support recursion but a function must be explicitly marked to allow it. This is enforced implicitly because a function can only call functions defined previously in the source code.

Then there are languages like C macros which are evaluated by textual substitution. This can't support recursion since the expansion would never stop and lead to an infinite size program.

While all general-purpose languages support recursion these days, there are a number of special-purpose languages (DSL's) which don't. For example CSS allows you to use built-in functions, but doesn't allow you to define your own, so there's no way to define a recursive function.

It is worth noting there's a class of languages which are called "stackless" but nevertheless do support function calls and recursion. They are called so because they don't use the regular stack as call stack but instead store the call frames in some heap-allocated structure like a linked list. But it's still a call stack, it's just implemented differently.

Answer 3

Kilian's answer states that:

every recursive program must contain at last one syntactical forward reference

However, if a language supports passing functions as arguments to other functions, it's possible to write recursive code without any forward references.

One way of doing this is to have a recursive function that takes itself as the first argument, so you can make recursive calls by referring to the first argument instead of using the function name directly. This isn't a forward reference because it's not using the function name.

Then when you call the function, you would pass in the same function as the first argument. This isn't a forward reference either, because the function has already been defined.

Here's a code example in Python, which uses recursion to compute factorials, and has no forward references:

def _fact(rec, n): # rec is actually _fact
    if n == 0:
        return 1
    return n * rec(rec, n - 1)

def fact(n):
    # pass _fact to itself so it can make recursive calls
    return _fact(_fact, n)

print(fact(3)) # outputs 6

(Maybe this answer should be a comment instead, but I don't have enough reputation to comment.)

Answer 4

It's extra work to support recursion. The compiler has a data structure called a symbol table that's a list of names of variables or functions and a pointer to their generated code. So if it sees a function call like factorial(10), it looks up in the symbol table where the factorial code is, puts a 10 in the arguments, and generates a function call to that address.

The problem with recursion is when the compiler is generating the code for the factorial function body, it sees a function call to factorial(n - 1), and looks in it's symbol table for where factorial is located, and it can't find it, because it doesn't exist yet, because the compiler is in the middle of generating it.

So what you have to do to support recursion is go through and make placeholders for all the function names first, then generate the code, then resolve all the references. That's not super difficult, but it is extra work and extra complexity.

Answer 5

The easiest way to disallow recursion is for the compiler to emit code which makes it a run-time check.

When you disallow recursion, it means that a procedure can have at most one activation at a time. You can associate a procedure with a flag which indicates whether it is active. If it is activated while that flag is active, you can abort the program.

If a language doesn't allow recursion, it doesn't require a dynamic stack. Since each procedure can have only one activation, its parameters do not have to be allocated dynamically; each procedure can have a static area where it receives parameters, and where it produces a return value. When a procedure is called, values are copied into that area to achieve parameter passage, and then afterward a value copied out of the return area to complete the return. The parameter area can hold the return address also.

In this same parameter area, you would have the flag indicating that the function is busy executing and cannot be called again. And witth these static areas, you could document an excellent reason why the function cannot be called: the interrupting call would clobber the statically allocated parameter area, and statically allocated locals.

I'm assuming that if a language forbids recursion, then all re-entry of a function (threads, interrupts) is likewise off the table. It would be somewhat logically inconsistent to be vehement about disallowing recursion, but allow a function to be spontaneously re-entered by multiple threads, or out of an interrupt service routine.

Anyway, under a run-time checking scheme, the compiler could still catch obvious cases of recursion statically, but without having to catch all cases. Being relaxed about it would mean flexible support for separate compilation. Under separate compilation, we cannot be sure whether recursion is going on or not.

If we have some external function procedure F() in another, separately compiled module, which we are calling out of G(), we cannot be sure that F() doesn't contain a call back to G(). A strict module scheme, like Modula-2-style modules, could be used to prevent that. Under modules, G() would be in module A, and F() would be in module B. A would declare that it's a client of module B, and we would have the rule that a client can call into a module which it uses, but a call in the other direction is forbidden. The compiler has the graph of all module dependencies and checks there are no cycles in it, and the calls among the modules can be constrained to follow the graph direction.

With run-time checks, we could allow circular references among modules while nevertheless banning recursion.

We could also allow indirect procedure calls while banning recursion. E.g. G() could call F(), passing it the address of callback H(). Since H() isn't G(), and doesn't call G(), everything is fine: no recursion.

Answer 6

If your language has function calls, a compiler will make function calls work, and it will make function calls from a called function work, and so on.

I’ve seen one processor and Fortran compiler that didn’t support recursion. That was because the “subroutine call” instruction actually write a jump instruction to the caller into the code of the called function. This means a called function has only one point it can return to, recursive functions must have two calls from different places, so one of the returns cannot work.

Note: If A called X and X returned, then B called X and x returned and so on, that would work just fine. At runtime X would have one return address (a different one on each call). A recursive function needs to handle two different simultaneous return addresses: Your calls form a cycle so the function is called once from outside and once from inside the cycle.

Answer 7

Having used such an environment, the compiler doesn't enforce the rule. In theory, the compiler could traverse the call graph and barring exotic situations emit an error message if recursion were possible by call graph. In practice, I have not encountered a compiler that did so.

What actually happens is if you attempt recursion when the target platform doesn't support it is you get an infinite loop, and if the target platform supports it you get recursion with a good chance of trashing your local variables because they weren't local after all.

If the target says no recursion, then don't write recursive functions.

Answer 8

I'm recently learning the programming language, and I wonder how compilers work when the language itself does not allow recursion, like how the compiler or the runtime checkers makes sure that there is no recursion.

Those are two very different questions. That a language does not support recursion does not imply that compilers or language runtimes must explicitly recognize and reject attempts to recurse.

The easiest alternative is simply not to check. That might have the result that recursion works in practice, even though it is not officially supported, or it might have the result that (some) recursive calls just don't work properly. For example, in a language that does not support recursion, an implementation might choose to allocate all functions' local variables statically, or on-demand persistently. In such a case, recursive execution of a function would clobber the values of local variables in other executions of that function. Disaster and mayhem would ensue.

On the other hand, if a language implementation wanted to actively enforce a rule against recursion then it would have a variety of alternatives, among them:

• Define language structure such that recursive calls cannot be expressed in the first place, such as by disallowing both forward references and indirect references to functions. OR

• Perform compile-time dependency analysis. In a compiled language, the compiler can, in principle, construct a call graph of which functions call which other functions. Recursive call chains correspond to loops in such a graph, and can therefore be detected by call-graph analysis. This can be defeated in a language that provides for function pointers / references, but that may be OK -- it is plausible that a language implementation would be satisfied to not detect recursion involving such calls (see above). OR

• Perform runtime recursion checks. It is possible to dynamically determine at function call time what other functions are currently executing, and thereby to detect recursive calls even when made indirectly via function pointers or similar. That would add some expense to function calls, but if implemented as part of the language then the performance impact could be controlled. Or, easier, it would be possible for each function to maintain a static flag indicating whether it itself was already running, which the implementation would test at function entry to detect attempts to recurse.

I learned that compilers don't need to understand recursion when translating the code, but how does one work without understanding it?

The point there is that recursion is not necessarily a case that requires special handling. Although there are design choices that a language implementation might make that would interfere with recursion or require special handling for recursive calls, the most natural choices for today's common machine architectures do not. Recursion falls out naturally as a case supported by the general function-call semantics.

I try to think to allocate a specific size of stack to avoid recursion, but then I think I have no idea about how to determine the size.

And you make my point by assuming that there is a stack, and that modifying its properties would impact the feasibility of recursion. Substantially all computers today do have a stack and do use it for supporting functions' local variables, and that is perhaps the main thing that makes recursion fall out naturally. But computers provide stacks because that turns out to be very useful, not because it's an inherent requirement for a computing device. And language implementations use stacks that way because it is very effective (and has nice implications such as supporting recursion), not because it's the only possible alternative.

I assume that it is not the language don't have recursion feature but the compilers or checkers don't allow.

That is not a safe assumption. As described above, it is entirely possible that the design of a language inherently makes recursion difficult or impossible, or that a compiler or language runtime makes choices that are incompatible with recursion without actively checking for recursive call chains. Or simply that the language specifications forbid recursion, regardless of what specific implementations support or check.