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.

  • 16
    Can you clarify what exactly you are asking? I.e. if language does not allow recursion (no function pointers/no forward declarations) why do you think some special actions need to "avoid recursion"? Commented Oct 6, 2022 at 16:17
  • 1
    ^ And speaking of that topic. I learned programming first on 8 bit microcomputers, using line-numbered BASIC which didn't support recursion. I think I first learned about recursion from Rodney Zaks' book Programming the 6502, which was about machine language. That has a binary search tree implementation with a recursive search, described succintly in Pascal-like pseudo-code and implemented in 6502 assembly, which was eye opening.
    – Kaz
    Commented Oct 7, 2022 at 7:02
  • 10
    @Kaz Higher level languages don't add to low-level machine instructions, they constrain them for the benefit of human users who want to impose structure on a program. One of those constraints is that you don't jump to arbitrary points of code, only to "function entry points"; another is that you don't access arbitrary memory locations, only "in-scope variables". Recursion (and, more simply, re-entrancy) requires a more complex implementation of those constraints.
    – IMSoP
    Commented Oct 7, 2022 at 9:54
  • 1
    @Kaz That is a very narrow view of what makes programming languages useful. There are several settings where it's nice to have the language guarantee that all of your programs eventually stop, for example; removing recursion could be one of the things a language could choose to do to help achieve that. Commented Oct 7, 2022 at 14:24
  • 10
    It should be noted that the language not supporting recursion doesn't mean you can't implement recursive solutions; it just means you need to do a lot more work (implement your own stack, write the control logic to push and pop states and to exit when the stack empties, and so on). This is part of what Turing compleness s about. Of course there may be resource limitations which limit how deeply you can recourse, tied to maximum size of that stack.
    – keshlam
    Commented Oct 7, 2022 at 20:54

8 Answers 8


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.

  • 19
    In a language that allows passing functions as arguments, no syntactical forward reference is required. Example in Julia: ``` function fib(n,f) return n<2 ? n : f(n-1,f) + f(n-2,f) end fib(10,fib) ``` Commented Oct 7, 2022 at 4:27
  • 23
    That's true, higher-order functions can circumvent this. A language with higher-order functions but without recursion would indeed have trouble detecting and banning recursion at compile-time. (Of course, such a feature combination would be really strange.) Commented Oct 7, 2022 at 6:21
  • 1
    Separate compilation could also defeat this --- unless you have strict modules like Modula 2, whereby a module has to declare that it uses another one, and the function calls can only go in that direction.
    – Kaz
    Commented Oct 7, 2022 at 6:35
  • 1
    I'm pretty sure that back in the mists of time I used versions of Fortran and COBOL that did allow forwards references but didn't allow recursion. So while forbidding forwards references forbids recursion, it also forbids other things as well. Commented Oct 7, 2022 at 14:13
  • 4
    Traditional non-recursive languages (form the 60's) absolutely allowed forward referencing. As non-intuitive as it may seem from this perspective "Forward-only referencing" was primarily a feature mostly featured in the "newer" recursive languages of the 70's and 80's. The reason for this was to allow the creation of one-pass compilers, and the solved they problem that this created for recursion by allowing the separation of declarations and definitions. Commented Oct 8, 2022 at 12:33

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.

  • 2
    @csxyyyyy: It means the return address of a function is fixed at compile time - the function will always return to the same place when called. There is no call stack involved.
    – JacquesB
    Commented Oct 6, 2022 at 19:58
  • 4
    "It means the return address of a function is fixed at compile time" - no, that would mean each function could only be called from one place, which would make them kind of useless. "Languages in the ML family (like F#) support recursion but a function must be explicitly marked to allow it" - not really accurate. let vs let rec is only about the scope of the function's name. The function itself can always be called recursively (see this comment).
    – benrg
    Commented Oct 7, 2022 at 6:21
  • 1
    @benrg: You are right, the return address change depending on where the function is called from. But there is just a single "slot" per function for storing the return address, rather than a call stack. So if you call a function recursively, the return address will just be overwritten which means the function can never exit.
    – JacquesB
    Commented Oct 7, 2022 at 13:03
  • 3
    @Barmar: GOSUB/RETURN does allow a form of recursion since it uses a call stack. But since it doesn't support parameters and return values like a real function call, recursion is of limited use.
    – JacquesB
    Commented Oct 7, 2022 at 14:14
  • 1
    True, although you could implement it yourself with an array and index.
    – Barmar
    Commented Oct 7, 2022 at 14:30

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.)

  • This is essentially a lightweight Y combinator
    – slebetman
    Commented Oct 7, 2022 at 6:58
  • 5
    First-class functions but no recursion, what a weird combination.
    – Barmar
    Commented Oct 7, 2022 at 14:00
  • 1
    @Barmar - you don't need proper first class functions for this to work, though -- just a "function pointer" as for example you would find in C or in some dialects of Pascal.
    – occipita
    Commented Oct 7, 2022 at 15:43
  • True, anything that represents a function. Of course, any language that prohibits recursion is weird to begin with. Early languages did this for simplicity, we've grown beyond that.
    – Barmar
    Commented Oct 7, 2022 at 15:45
  • 6
    @Barmar: Languages that allow recursion generally use "hope for the best" semantics regarding stack availability; for many purposes, a guarantee that a lack of memory will result in a build failure rather than arbitrary nonsensical behavior at runtime may offer far more benefit than recursion could.
    – supercat
    Commented Oct 7, 2022 at 22:17

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.

  • 1
    This is basically the "forward reference" problem in Killian's answer.
    – Barmar
    Commented Oct 7, 2022 at 13:58
  • 4
    A function calling itself doesn't have this problem: Even if the compiler hasn't finished generating factorial yet; it still knows where the function starts. The complexity comes where you have mutual recursion, where A calls B and B calls A, but the compiler doesn't know where to put B until it's finished generating A's code.
    – dan04
    Commented Oct 7, 2022 at 19:27
  • Don't use standard libraries I see. If you can use precompiled libraries you can express recursion.
    – Joshua
    Commented Oct 8, 2022 at 0:45
  • 1
    @dan04: Even that isn't hard to handle. A compiler which encounters a forward declaration for function "foo" can create a hidden "global variable" that will be used to hold the address of foo, process any requests to call foo as indirect function calls, and then after it has compiled everything else generate code for a startup function that will initialize all such function pointers.
    – supercat
    Commented Oct 8, 2022 at 20:51

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.


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.


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.


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.