Skip to main content
24 votes

What is the use of explicitly specifying if a function is recursive or not?

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 ...
Michael Homer's user avatar
  • 13k
16 votes
Accepted

How can we define a denotational semantics for recursive functions?

One way to represent this kind of (computable) recursive function mathematically comes from domain theory. I will end up describing something called a Scott domain in this answer, named after Dana ...
David Young's user avatar
  • 2,257
15 votes

What is the use of explicitly specifying if a function is recursive or not?

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 ...
Nate Eldredge's user avatar
14 votes
Accepted

Early binding, mutual recursion, closures. Can I have all three?

This doesn't require late binding, just forward references. That is, the name say_b appears in the code before it's declared. Late binding is one way of supporting ...
kaya3's user avatar
  • 19.7k
13 votes
Accepted

Dynamic and Static scoping and recursion

I'll assume that b = 2; is meant to be a declaration of a new variable, rather than an assignment to an existing one (because otherwise this is trivial). Let's try ...
Michael Homer's user avatar
  • 13k
13 votes

What are the trade-offs in supporting Tail Recursion Optimization, but not Tail Call Optimization?

The major advantage of TRO is that it's (often much) easier to implement: a purely local analysis can inspect the final statement and convert the function body to a loop. In all other technical ...
Michael Homer's user avatar
  • 13k
10 votes
Accepted

Is there a generic way to refer to the current function in recursion?

APL A few APL dialects support the glyph inside a dfn (which is pretty much a lambda) which refers to the dfn itself. See Dyalog documentation on recursion. (I ...
RubenVerg's user avatar
  • 1,632
9 votes

Early binding, mutual recursion, closures. Can I have all three?

When you talk about function closures, what you actually seem to have in mind is anonymous functions, which are an entirely different and orthogonal concept. Under Python semantics, your ...
benrg's user avatar
  • 479
8 votes

Early binding, mutual recursion, closures. Can I have all three?

Explicit early- vs late-binding Swift will let you immediately initialize only one of the closures, and you must explicitly defer initialization of the other: ...
Bbrk24's user avatar
  • 9,067
7 votes

Is there a generic way to refer to the current function in recursion?

Forth Recursion in Forth actually requires a construct like this, as a word is not visible inside its own definition. In order to recurse, you need to use the ...
jwodder's user avatar
  • 171
7 votes

Early binding, mutual recursion, closures. Can I have all three?

Yes, you can do this. There are two obvious approaches to this: one is the approach taken by Scheme, and the other is the approach taken by, really, the λ-calculus. As this is not a language-specific ...
ignis volens's user avatar
7 votes

Early binding, mutual recursion, closures. Can I have all three?

You sure can. The big question is: when a function mentions the name of a variable or another function, does it see the static, known-at-compile-time value of the variable, the run-time value that ...
Tanner Swett's user avatar
7 votes

Early binding, mutual recursion, closures. Can I have all three?

Correct me if I'm wrong, but doesn't C# already have this feature? Here is your pseudocode translated to C#: Correction: C# almost has this feature. As pointed out by Tanner Swett in the comments, ...
Vilx-'s user avatar
  • 211
7 votes

What are the trade-offs in supporting Tail Recursion Optimization, but not Tail Call Optimization?

useful applications of TCO that TRO can't handle Having Proper Tailcalls, i.e. TCO that is mandated by the language specification and implemented by all implementations (as in Scheme) allows to write ...
Jörg W Mittag's user avatar
6 votes

How to optimize non-tail recursion?

Last call modulo constructor One common situation in declarative languages is where there is almost a tail call, in the sense that there are no computations or calls (or ABI infrastructure, such as ...
Pseudonym's user avatar
  • 4,726
6 votes

Dynamic and Static scoping and recursion

Scope and extent In Lisp there is both lexical and dynamic scoping, and the language relies on two concepts to explain bindings: scope which is related to space Where can you refer to this binding? ...
coredump's user avatar
  • 923
6 votes

Does x86 assembly support linguistic recursion?

It's not immediately clear how we should even define linguistic recursion as a property of a formal language. We can certainly define it as a property of a grammar. For example, supposing ...
kaya3's user avatar
  • 19.7k
5 votes

Is there a generic way to refer to the current function in recursion?

Mathematica, a definition of the factorial function: If[#1 == 1, 1, #1 #0[#1 - 1]]& (The ampersand indicates a definition of an anonymous function; ...
Patrick Stevens's user avatar
5 votes

Is there a generic way to refer to the current function in recursion?

In Perl — which is not primarily a functional language, but does support functional programming styles — the keyword __SUB__ is a reference to the current ...
ruakh's user avatar
  • 153
5 votes

What is the use of explicitly specifying if a function is recursive or not?

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 ...
Eldritch Conundrum's user avatar
5 votes
Accepted

Can total (primitive) corecursion be implemented?

Such elements correspond to infinite constructor applications. In the case of $\tilde{\mathbb{N}}$, the element at infinity will correspond to succ(succ(succ(...)))....
David Young's user avatar
  • 2,257
4 votes

What are the trade-offs in supporting Tail Recursion Optimization, but not Tail Call Optimization?

If you implement TRO but not TCO then a programmer may have fewer options to refactor a complex tail-recursive function. For example, they couldn't, without affecting stack usage, split code that ...
Mike Samuel's user avatar
4 votes
Accepted

X86-64 Assembly for Recursive Functions

Your way of aligning the stack messes with the restoration of saved registers. You should keep track of stack alignment in the compiler, and manage it with sub and <...
abel1502's user avatar
  • 2,527
4 votes

What is the use of explicitly specifying if a function is recursive or not?

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 (...
Jay Lee's user avatar
  • 223
3 votes

What is the use of explicitly specifying if a function is recursive or not?

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 ...
Audrius Meškauskas's user avatar
3 votes

Is there a generic way to refer to the current function in recursion?

C++ Since C++23 you can add an explicit object parameter to member functions and lambdas. You still have to give the parameter a name, but you would typically use ...
G. Sliepen's user avatar
3 votes

Is there a generic way to refer to the current function in recursion?

In R we have Recall. From the docs we see (calling ?Recall): ...
Joseph Wood's user avatar
3 votes

Is there a generic way to refer to the current function in recursion?

In JavaScript, arguments.callee could be used, but it is now deprecated and invalid in strict mode. ...
corvus_192's user avatar
3 votes

Does x86 assembly support linguistic recursion?

There's no standardized assembly language for most popular CPU architectures. X86 has masm, nasm and gas for starters, each with its own mutually incompatible directives and macro system. In nasm you ...
benrg's user avatar
  • 479
2 votes

Extending Hindley Milner with (mutual) recursion

Yes, and this is essentially what OCaml does, actually.
xuq01's user avatar
  • 161

Only top scored, non community-wiki answers of a minimum length are eligible