<p>In some languages, such as F# and FORTRAN, a keyword is used to specify if a function is recursive or not. What is the use of this, other than telling whoever is using the code that the function is recursive?</p>

<recursion>
What is the use of explicitly specifying if a function is recursive or not?
<p>One variation on this is that enabling tail-call elimination is slightly sub-optimal on some architectures if you don’t use it, and also makes it harder to get a stack trace for debugging.  It can also cause problems with freeing local variables.  Therefore, high-performance languages like C, C++ and Rust usually don’t have it by default.</p>
<p>However, some algorithms really, really need this optimization.  So Clang and some other compilers have a keyword that forces the compiler to optimize a recursive or mutually-recursive tail call.  Rust will be adding the <code>become</code> keyword for this as well.</p>

CC BY-SA 4.0
2023-07-28T20:56:47.923Z
2023-07-28T20:56:47.923Z
Davislor
<p>A language that provides a keyword to mark a recursive function can often detect the unintended recursive call at the compilation time. This bug sometimes happens and very indirect recursion (A calls B, B calls C .... Z calls A) may not be very trivial to see. Infinite recursion may sometimes be difficult to diagnose, just hanging the program without any obvious hint why.</p>

CC BY-SA 4.0
2023-07-28T16:43:08.820Z
2023-07-28T16:43:08.820Z
Audrius Meškauskas
<p>There are a few different elements here; some are historical contingencies, some are philosophical, and some are enabling certain patterns.</p>
<ul>
<li><p>What F# <code>let rec</code> does is <strong>make the name of the function available within the function body</strong>. With bare <code>let</code>, it runs with the same bindings as on the previous line. This distinction allows defining a new function that shadows an existing one, but has access to the original internally.</p>
<p>Sometimes this is useful, though maybe not enough to justify being so explicit universally. In a language where recursion is always available, the different versions need to be given different names (either initially, or by aliasing).</p>
</li>
<li><p>There can also be some implementation benefits to declaring recursion explicitly, albeit of more limited use today than previously. Many compilers aim for a <strong>single pass where code is processed top-to-bottom only</strong>. This saves resources, notably memory, and can make the compiler simpler.</p>
<p>This <em>might</em> be able to handle self-recursion, but for <strong>mutually-recursive functions</strong> it inherently can't: one function must always be defined later than another, so it's necessary to parse ahead to collect available names at the least. Explicit <code>let rec</code> declares that this may be happening, so the compiler knows it doesn't have to do it other times. There is a <strong>compile-time cost to allowing mutual recursion</strong>, and the programmer can choose when to pay that price during compilation, and potentially <em>how much of it</em> to pay by keeping those functions small.</p>
<p>The resource costs of multi-pass compilers are much less significant now than they once were, and most modern languages don't aim for it. Languages that that did need to care about this at their creation have committed to the design choices already.</p>
</li>
<li><p>In some systems, local variables and return addresses are typically statically allocated <em>per-function</em>: a function running only one instance at a time allows this, but a function that can appear many times in the call stack needs to hold onto many return addresses and many slots for its local variables. This is a <strong>run-time cost that potentially-recursive functions pay</strong>, even when they're not used recursively.</p>
<p>Explicitly identifying which this is allows using the cheap, quick, optimal version everywhere that can get away with it, and rejecting programs that break those rules. This is, again, less common today, but embedded systems may have enough constraints for it to be worthwhile.</p>
</li>
<li><p>When recursion wasn't originally permitted at all and is introduced in a later version, <strong>making it opt-in ensures that existing code isn't broken</strong>.</p>
<p>For Fortran, the typical style of returning a value is assignment to the function name — but in a recursive function you have to specify <em>another</em> variable to use instead, because the function name is used for the recursive calls. This will have made porting Fortran 77⇒90 easier, while otherwise fitting within the language ethos.</p>
</li>
<li><p>More philosophically, annotating a function as recursive is invoking use of the fixed-point Y combinator <code>λf. (λx. f (x x)) (λx.  f (x x))</code> for defining a function that has access to itself, and is notionally doing that extra work; this is rare in practical languages.</p>
</li>
<li><p>Considering the <code>let</code> construction more mathematically, in a longer form that many languages permit:</p>
<pre class="lang-hs prettyprint-override"><code>let f = ... in map f
</code></pre>
<p>The <code>in</code> here delimits a scope where the name is defined. <code>f</code> is created <em>outside</em> that scope, so it wouldn't be expected to see the name being created. Often the scope is permitted to be just the rest of the file implicitly, but written out explicitly the delineation is more clear.</p>
</li>
</ul>
<p>However, none of this is <em>necessary</em> as a language element, even within the same language family. CAML and derivatives have it (including F#), and SML and derivatives don't (including Haskell). It may be necessary for some specific target <em>platforms</em>, and you'll probably know if you're in that scenario.</p>

CC BY-SA 4.0
2023-07-28T06:13:48.490Z
2023-07-29T11:20:38.807Z
2023-07-29T11:20:38.807Z
Michael Homer
CC BY-SA 4.0
2023-07-28T17:18:47.057Z
Another benefit is that if a language provides a conditional check for whether adequate stack space is available, and regards as a "checked recursive function" one where any calls to unchecked recursive functions exist on "true" branches of such checks, then it will be possible to statically compute maximum stack usage needed to safely process without stack overflow a program that never calls unchecked recursive functions.
supercat
CC BY-SA 4.0
2023-07-29T07:21:28.733Z
This answer mixes F# and FORTRAN in a confusing way, potentially leaving readers with the wrong impression that non-recursive `let` in F# is enough to ensure there is no recursion (so you could use static storage instead of a stack for functions declared that way). See Eldritch Conundrum's answer and my comment.
benrg
CC BY-SA 4.0
2023-07-29T07:50:16.970Z
I don't think it *should* give that impression, given that F# obviously has first-class functions, but in any case only one point is specifically about each of them and those are very far apart. They all ought to be read independently, but edits welcome if they don't come over that way.
Michael Homer
CC BY-SA 4.0
2023-07-29T10:30:52.860Z
Typed languages are not using the Y combinator, because it is not well typed (in nearly all type systems). Standard typed core languages, like PCF, contain a primitive fixpoint construct, which is given its own semantics.
James Wood
CC BY-SA 4.0
2023-07-29T11:22:22.517Z
The popular languages from the 60's and early 70's  (FORTRAN and COBOL) did not originally allocate routine-local storage (for functions *and* subroutines) dynamically off the the stack, but rather had fixed allocation of local variables at a static address associated with each separate routine.  This was the original primary reason why they didn't originally support recursion (or dynamic-length structures (except for FORTRAN strings which were indirectly allocated from a heap)).  Obviously if a compiler were still allocating this way, it would need to know when to allow for reentry.
RBarryYoung
CC BY-SA 4.0
2023-07-30T00:15:54.207Z
> When recursion wasn't originally permitted at all and is introduced in a later version, making it opt-in ensures that existing code isn't broken.
I'm sure this is related to function name being used in variables/other internal functions, but what are the cases where it being auto-enabled would break older non-recursive code?
kouta-kun
CC BY-SA 4.0
2023-07-30T00:42:30.183Z
@kouta-kun Anything that changes the meaning of an identifier can break existing code, including the function shadowing from the first point, use as an ordinary variable name, or F77 returns, but even the static/dynamic allocation changes could be a problem — *all* the listed points except the philosophical ones are potential compatibility breaks if code previously relied on the original behaviour.
Michael Homer
<p>If a function won't be called recursively, it does not need to use a stack to save its return address.</p>
<p>Modern CPUs tend to have hardware stack instructions that make it convenient to save return addresses on a stack, which means that all functions can be called recursively without doing anything special.  But they could be stored somewhere else.</p>
<p>One possible convention is that you allocate one memory slot <em>per function</em> where every call to that function will save their return address.  For instance, you might use the word immediately preceding the first instruction of the function.  <a href="https://en.wikipedia.org/wiki/Function_(computer_programming)#Jump_to_subroutine" rel="noreferrer">Wikipedia</a> mentions the HP 2100 as a machine whose Jump Subroutine instruction (JSB) worked this way.  Another way is to pass the return address in a designated register; but instead of having the called function store this on the stack, it can write it directly into a jump instruction appearing at the end of the function (self-modifying code).  This method doesn't require the machine to have a special return instruction nor even an indirect jump.</p>
<p>So a function that won't be called recursively can use such a method.  Only functions that actually are potentially recursive need to pay the additional cost of pushing to a stack.</p>

CC BY-SA 4.0
2023-07-28T06:04:06.740Z
2023-07-28T06:04:06.740Z
Nate Eldredge
CC BY-SA 4.0
2023-07-28T06:21:07.593Z
On modern hardware, is the costs of pushing to the stack higher than setting the memory slot?
a coder
CC BY-SA 4.0
2023-07-28T06:24:14.750Z
@acoder: On modern hardware, the stack is better.  With memory protection, the code itself and surrounding memory are usually not even writable at all.  Even if they were, the stack is a heavily used area of memory and therefore more likely to be hot in the data cache.
Nate Eldredge
CC BY-SA 4.0
2023-07-28T06:31:27.497Z
What happens in FORTRAN if a function is not labelled as recursive, but then attempts mutual recursion with another function?
Karl Knechtel
CC BY-SA 4.0
2023-07-28T06:34:00.893Z
@KarlKnechtel: I'd presume you get undefined behavior (or whatever FORTRAN calls it).  https://www.intel.com/content/www/us/en/docs/fortran-compiler/developer-guide-reference/2023-1/recursive-and-non-recursive.html says that `recursive` (when not the default) needs to be used whenever the function may call itself directly or indirectly.
Nate Eldredge
CC BY-SA 4.0
2023-07-28T14:11:10.527Z
I cut my assembly teeth on the PDP-8, and its JSUB also worked this way.
Barmar
CC BY-SA 4.0
2023-07-28T20:18:25.383Z
@acoder The thing is though, you're really not very likely to be writing Fortran to run on modern hardware. It's not quite a dead language, but its family are definitely talking about DNR orders. :/ As a language designed at a time when processing resources were in seriously short supply, you can expect features to let you optimise this to save a few bytes here and there.
Graham
CC BY-SA 4.0
2023-07-28T21:28:27.147Z
A related design decision is whether to store local variables on the stack or in a single location for all invocations.  On many older architectures, accessing data stored on the stack was slower than directly addressing a known memory location, or may have had limited size stacks (e.g. the 6502 CPU only allowed 256 bytes for stack, because it was referenced by an 8 bit pointer), but of course always using the same location is not compatible with recursion.
occipita
CC BY-SA 4.0
2023-07-28T21:32:12.867Z
Many years ago when I wrote FORTRAN code, the subroutine call instruction (call X) from location Y would write a "JMP Y+1" instruction to location X, and start execution at X+1. In order to return, the function would branch to location X and execute the JMP instruction stored there. If you managed a recursive call, returning would always return to the location of the last call. So the recursive calls would return correctly, but the first call to the function from the outside wouldn't.
gnasher729
CC BY-SA 4.0
2023-07-29T09:19:25.873Z
There certainly _are_ a few places where FORTRAN is in active use (and new code is being written), such as scientific or technical computing; when runtimes are measured in days or weeks, the better optimisation of FORTRAN compilers can be a significant factor.
gidds
CC BY-SA 4.0
2023-07-29T09:20:49.320Z
Wouldn't storing return addresses in a memory slot be incompatible with multithreading? (Unless each thread had its own set of memory slots, of course — but I don't think the answer is talking about that.)
gidds
CC BY-SA 4.0
2023-07-29T16:43:15.163Z
@gidds: Yes, of course this would not work at all with multithreading.  Effectively the function becomes non-reentrant.  This is a very old and obsolete technique and I don't think multithreading was on anybody's mind at the time.
Nate Eldredge
CC BY-SA 4.0
2023-07-30T17:57:06.400Z
@gidds: For high-performance computing applications, having each core run code from a bank of memory which is connected exclusively to that core would be more efficient than having code run from a shared memory.  Even though cores would presumably have caches, they would still need to include logic to arbitrarte potential contention which could be omitted if code fetches by any core were all performed from RAM banks that were devoted to that core.
supercat
CC BY-SA 4.0
2023-07-30T19:12:28.710Z
@supercat I didn't intend those two comments to be considered together :-) (As you say, it's more efficient for each node to have its own memory, as per [MapReduce](https://en.wikipedia.org/wiki/MapReduce); ideally you'd have clever algorithms dividing the work into separate tasks for all the nodes, each tuned to need as little intercommunication as possible. But I don't know any details.)
gidds
<p>I think the main reasons why it's in F# and ocaml are already in Michael Homer's answer (avoiding to shadow a similar identifier, and enabling a function to exceptionally use an identifier defined below it), but I have one more to add.</p>
<p>Just like <code>unsafe</code> (in e.g. Rust) is a useful keyword because its absence guarantees the safety, <code>rec</code> is a useful keyword because its absence guarantees the absence of stack overflow due to infinite recursion.</p>

CC BY-SA 4.0
2023-07-28T07:00:41.613Z
2023-07-28T07:00:41.613Z
Eldritch Conundrum
CC BY-SA 4.0
2023-07-29T07:16:16.480Z
"because its absence guarantees the absence of stack overflow due to infinite recursion" - no, it doesn't. You can still get recursion indirectly through some Y-combinator-like construction. It prevents accidental recursion, but the type system tends to catch that anyway.
benrg
CC BY-SA 4.0
2023-07-30T22:44:38.180Z
@benrg You can only build an Y-combinator if you have a a way of passing functions to other functions. If your language doesn't have that, there is no risk.
Paŭlo Ebermann
<p>I want to note that explicit recursive definition in OCaml, i.e., <code>let rec</code>, is not limited to defining a function.</p>
<p>One can go on and define self-referential values (with some restrictions):</p>
<pre class="lang-ocaml prettyprint-override"><code>type t = { self : t }
let rec circular = { self = circular }
</code></pre>
<p>which creates</p>
<pre class="lang-ocaml prettyprint-override"><code>val circular : t = {self = &lt;cycle&gt;}
</code></pre>
<p>Although one might prefer letting <code>let circular = { self = circular }</code> to create <code>{self = &lt;cycle&gt;}</code>.
So I'd say this is largely a matter of taste.</p>
<p>At the end of the day, distinction between <code>let</code> and <code>let rec</code> provides the user an opportunity to explicitly choose between using two typing rules:</p>
<pre class="lang-ocaml prettyprint-override"><code> Γ ⊢ e : T   Γ, x : T ⊢ e' : T'
--------------------------------
    Γ ⊢ let x = e in e' : T'
</code></pre>
<p>and</p>
<pre class="lang-ocaml prettyprint-override"><code> Γ, x : T ⊢ e : T    Γ, x : T ⊢ e' : T'
----------------------------------------
      Γ ⊢ let rec x = e in e' : T'
</code></pre>
<p>Perhaps this is in a smilar spirit to providing both <code>let x = e in e'</code> and <code>let x = e and y = e' in e''</code> bindings, which also exposes an extra nob to fine-control the scope of an environment.</p>

CC BY-SA 4.0
2023-07-30T00:50:06.470Z
2023-07-30T00:50:06.470Z
Jay Lee
# What is the use of explicitly specifying if a function is recursive or not?
Posted by: username_0 on 2023-07-28
In some languages, such as F# and FORTRAN, a keyword is used to specify if a function is recursive or not. What is the use of this, other than telling whoever is using the code that the function is recursive?
**Tags:** recursion
---
## 6 answers
### Answer by username_3 on 2023-07-28. Score: 24
There are a few different elements here; some are historical contingencies, some are philosophical, and some are enabling certain patterns.

What F# let rec does is make the name of the function available within the function body. With bare let, it runs with the same bindings as on the previous line. This distinction allows defining a new function that shadows an existing one, but has access to the original internally.
Sometimes this is useful, though maybe not enough to justify being so explicit universally. In a language where recursion is always available, the different versions need to be given different names (either initially, or by aliasing).

There can also be some implementation benefits to declaring recursion explicitly, albeit of more limited use today than previously. Many compilers aim for a single pass where code is processed top-to-bottom only. This saves resources, notably memory, and can make the compiler simpler.
This might be able to handle self-recursion, but for mutually-recursive functions it inherently can't: one function must always be defined later than another, so it's necessary to parse ahead to collect available names at the least. Explicit let rec declares that this may be happening, so the compiler knows it doesn't have to do it other times. There is a compile-time cost to allowing mutual recursion, and the programmer can choose when to pay that price during compilation, and potentially how much of it to pay by keeping those functions small.
The resource costs of multi-pass compilers are much less significant now than they once were, and most modern languages don't aim for it. Languages that that did need to care about this at their creation have committed to the design choices already.

In some systems, local variables and return addresses are typically statically allocated per-function: a function running only one instance at a time allows this, but a function that can appear many times in the call stack needs to hold onto many return addresses and many slots for its local variables. This is a run-time cost that potentially-recursive functions pay, even when they're not used recursively.
Explicitly identifying which this is allows using the cheap, quick, optimal version everywhere that can get away with it, and rejecting programs that break those rules. This is, again, less common today, but embedded systems may have enough constraints for it to be worthwhile.

When recursion wasn't originally permitted at all and is introduced in a later version, making it opt-in ensures that existing code isn't broken.
For Fortran, the typical style of returning a value is assignment to the function name — but in a recursive function you have to specify another variable to use instead, because the function name is used for the recursive calls. This will have made porting Fortran 77⇒90 easier, while otherwise fitting within the language ethos.

More philosophically, annotating a function as recursive is invoking use of the fixed-point Y combinator λf. (λx. f (x x)) (λx.  f (x x)) for defining a function that has access to itself, and is notionally doing that extra work; this is rare in practical languages.

Considering the let construction more mathematically, in a longer form that many languages permit:
let f = ... in map f

The in here delimits a scope where the name is defined. f is created outside that scope, so it wouldn't be expected to see the name being created. Often the scope is permitted to be just the rest of the file implicitly, but written out explicitly the delineation is more clear.


However, none of this is necessary as a language element, even within the same language family. CAML and derivatives have it (including F#), and SML and derivatives don't (including Haskell). It may be necessary for some specific target platforms, and you'll probably know if you're in that scenario.
> **Comments:**
> **username_4** (2023-07-28): Another benefit is that if a language provides a conditional check for whether adequate stack space is available, and regards as a "checked recursive function" one where any calls to unchecked recursive functions exist on "true" branches of such checks, then it will be possible to statically compute maximum stack usage needed to safely process without stack overflow a program that never calls unchecked recursive functions.  
> **username_5** (2023-07-29): This answer mixes F# and FORTRAN in a confusing way, potentially leaving readers with the wrong impression that non-recursive `let` in F# is enough to ensure there is no recursion (so you could use static storage instead of a stack for functions declared that way). See Eldritch Conundrum's answer and my comment.  
> **username_3** (2023-07-29): I don't think it *should* give that impression, given that F# obviously has first-class functions, but in any case only one point is specifically about each of them and those are very far apart. They all ought to be read independently, but edits welcome if they don't come over that way.  
> **username_6** (2023-07-29): Typed languages are not using the Y combinator, because it is not well typed (in nearly all type systems). Standard typed core languages, like PCF, contain a primitive fixpoint construct, which is given its own semantics.  
> **username_7** (2023-07-29): The popular languages from the 60's and early 70's  (FORTRAN and COBOL) did not originally allocate routine-local storage (for functions *and* subroutines) dynamically off the the stack, but rather had fixed allocation of local variables at a static address associated with each separate routine.  This was the original primary reason why they didn't originally support recursion (or dynamic-length structures (except for FORTRAN strings which were indirectly allocated from a heap)).  Obviously if a compiler were still allocating this way, it would need to know when to allow for reentry.  
> **username_8** (2023-07-30): > When recursion wasn't originally permitted at all and is introduced in a later version, making it opt-in ensures that existing code isn't broken.
I'm sure this is related to function name being used in variables/other internal functions, but what are the cases where it being auto-enabled would break older non-recursive code?  
> **username_3** (2023-07-30): @kouta-kun Anything that changes the meaning of an identifier can break existing code, including the function shadowing from the first point, use as an ordinary variable name, or F77 returns, but even the static/dynamic allocation changes could be a problem — *all* the listed points except the philosophical ones are potential compatibility breaks if code previously relied on the original behaviour.  
---
### Answer by username_9 on 2023-07-28. Score: 15
If a function won't be called recursively, it does not need to use a stack to save its return address.

Modern CPUs tend to have hardware stack instructions that make it convenient to save return addresses on a stack, which means that all functions can be called recursively without doing anything special. But they could be stored somewhere else.

One possible convention is that you allocate one memory slot *per function* where every call to that function will save their return address. For instance, you might use the word immediately preceding the first instruction of the function. [Wikipedia](https://en.wikipedia.org/wiki/Function_(computer_programming)#Jump_to_subroutine) mentions the HP 2100 as a machine whose Jump Subroutine instruction (JSB) worked this way. Another way is to pass the return address in a designated register; but instead of having the called function store this on the stack, it can write it directly into a jump instruction appearing at the end of the function (self-modifying code). This method doesn't require the machine to have a special return instruction nor even an indirect jump.

So a function that won't be called recursively can use such a method. Only functions that actually are potentially recursive need to pay the additional cost of pushing to a stack.
> **Comments:**
> **username_0** (2023-07-28): On modern hardware, is the costs of pushing to the stack higher than setting the memory slot?  
> **username_9** (2023-07-28): @acoder: On modern hardware, the stack is better.  With memory protection, the code itself and surrounding memory are usually not even writable at all.  Even if they were, the stack is a heavily used area of memory and therefore more likely to be hot in the data cache.  
> **username_10** (2023-07-28): What happens in FORTRAN if a function is not labelled as recursive, but then attempts mutual recursion with another function?  
> **username_9** (2023-07-28): @KarlKnechtel: I'd presume you get undefined behavior (or whatever FORTRAN calls it).  https://www.intel.com/content/www/us/en/docs/fortran-compiler/developer-guide-reference/2023-1/recursive-and-non-recursive.html says that `recursive` (when not the default) needs to be used whenever the function may call itself directly or indirectly.  
> **username_11** (2023-07-28): I cut my assembly teeth on the PDP-8, and its JSUB also worked this way.  
> **username_12** (2023-07-28): @acoder The thing is though, you're really not very likely to be writing Fortran to run on modern hardware. It's not quite a dead language, but its family are definitely talking about DNR orders. :/ As a language designed at a time when processing resources were in seriously short supply, you can expect features to let you optimise this to save a few bytes here and there.  
> **username_13** (2023-07-28): A related design decision is whether to store local variables on the stack or in a single location for all invocations.  On many older architectures, accessing data stored on the stack was slower than directly addressing a known memory location, or may have had limited size stacks (e.g. the 6502 CPU only allowed 256 bytes for stack, because it was referenced by an 8 bit pointer), but of course always using the same location is not compatible with recursion.  
> **username_14** (2023-07-28): Many years ago when I wrote FORTRAN code, the subroutine call instruction (call X) from location Y would write a "JMP Y+1" instruction to location X, and start execution at X+1. In order to return, the function would branch to location X and execute the JMP instruction stored there. If you managed a recursive call, returning would always return to the location of the last call. So the recursive calls would return correctly, but the first call to the function from the outside wouldn't.  
> **username_15** (2023-07-29): There certainly _are_ a few places where FORTRAN is in active use (and new code is being written), such as scientific or technical computing; when runtimes are measured in days or weeks, the better optimisation of FORTRAN compilers can be a significant factor.  
> **username_15** (2023-07-29): Wouldn't storing return addresses in a memory slot be incompatible with multithreading? (Unless each thread had its own set of memory slots, of course — but I don't think the answer is talking about that.)  
> **username_9** (2023-07-29): @gidds: Yes, of course this would not work at all with multithreading.  Effectively the function becomes non-reentrant.  This is a very old and obsolete technique and I don't think multithreading was on anybody's mind at the time.  
> **username_4** (2023-07-30): @gidds: For high-performance computing applications, having each core run code from a bank of memory which is connected exclusively to that core would be more efficient than having code run from a shared memory.  Even though cores would presumably have caches, they would still need to include logic to arbitrarte potential contention which could be omitted if code fetches by any core were all performed from RAM banks that were devoted to that core.  
> **username_15** (2023-07-30): @supercat I didn't intend those two comments to be considered together :-) (As you say, it's more efficient for each node to have its own memory, as per [MapReduce](https://en.wikipedia.org/wiki/MapReduce); ideally you'd have clever algorithms dividing the work into separate tasks for all the nodes, each tuned to need as little intercommunication as possible. But I don't know any details.)  
---
### Answer by username_16 on 2023-07-28. Score: 5
I think the main reasons why it's in F# and ocaml are already in Michael Homer's answer (avoiding to shadow a similar identifier, and enabling a function to exceptionally use an identifier defined below it), but I have one more to add.

Just like `unsafe` (in e.g. Rust) is a useful keyword because its absence guarantees the safety, `rec` is a useful keyword because its absence guarantees the absence of stack overflow due to infinite recursion.
> **Comments:**
> **username_5** (2023-07-29): "because its absence guarantees the absence of stack overflow due to infinite recursion" - no, it doesn't. You can still get recursion indirectly through some Y-combinator-like construction. It prevents accidental recursion, but the type system tends to catch that anyway.  
> **username_17** (2023-07-30): @benrg You can only build an Y-combinator if you have a a way of passing functions to other functions. If your language doesn't have that, there is no risk.  
---
### Answer by username_18 on 2023-07-30. Score: 4
I want to note that explicit recursive definition in OCaml, i.e., let rec, is not limited to defining a function.
One can go on and define self-referential values (with some restrictions):
type t = { self : t }
let rec circular = { self = circular }

which creates
val circular : t = {self = }

Although one might prefer letting let circular = { self = circular } to create {self = }.
So I'd say this is largely a matter of taste.
At the end of the day, distinction between let and let rec provides the user an opportunity to explicitly choose between using two typing rules:
 Γ ⊢ e : T   Γ, x : T ⊢ e' : T'
--------------------------------
    Γ ⊢ let x = e in e' : T'

and
 Γ, x : T ⊢ e : T    Γ, x : T ⊢ e' : T'
----------------------------------------
      Γ ⊢ let rec x = e in e' : T'

Perhaps this is in a smilar spirit to providing both let x = e in e' and let x = e and y = e' in e'' bindings, which also exposes an extra nob to fine-control the scope of an environment.
---
### Answer by username_2 on 2023-07-28. Score: 3
A language that provides a keyword to mark a recursive function can often detect the unintended recursive call at the compilation time. This bug sometimes happens and very indirect recursion (A calls B, B calls C .... Z calls A) may not be very trivial to see. Infinite recursion may sometimes be difficult to diagnose, just hanging the program without any obvious hint why.
---
### Answer by username_1 on 2023-07-28. Score: 2
One variation on this is that enabling tail-call elimination is slightly sub-optimal on some architectures if you don’t use it, and also makes it harder to get a stack trace for debugging. It can also cause problems with freeing local variables. Therefore, high-performance languages like C, C++ and Rust usually don’t have it by default.

However, some algorithms really, really need this optimization. So Clang and some other compilers have a keyword that forces the compiler to optimize a recursive or mutually-recursive tail call. Rust will be adding the `become` keyword for this as well.
---
