20
$\begingroup$

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?

$\endgroup$

6 Answers 6

24
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – supercat
    Commented Jul 28, 2023 at 17:18
  • $\begingroup$ 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. $\endgroup$
    – benrg
    Commented Jul 29, 2023 at 7:21
  • $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Commented Jul 29, 2023 at 7:50
  • $\begingroup$ 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. $\endgroup$
    – James Wood
    Commented Jul 29, 2023 at 10:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – Michael Homer
    Commented Jul 30, 2023 at 0:42
15
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ On modern hardware, is the costs of pushing to the stack higher than setting the memory slot? $\endgroup$
    – a coder
    Commented Jul 28, 2023 at 6:21
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jul 28, 2023 at 6:24
  • $\begingroup$ What happens in FORTRAN if a function is not labelled as recursive, but then attempts mutual recursion with another function? $\endgroup$ Commented Jul 28, 2023 at 6:31
  • 1
    $\begingroup$ I cut my assembly teeth on the PDP-8, and its JSUB also worked this way. $\endgroup$
    – Barmar
    Commented Jul 28, 2023 at 14:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – occipita
    Commented Jul 28, 2023 at 21:28
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – benrg
    Commented Jul 29, 2023 at 7:16
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jul 30, 2023 at 22:44
4
$\begingroup$

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 = <cycle>}

Although one might prefer letting let circular = { self = circular } to create {self = <cycle>}. 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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .