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 ...
- 13.6k
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 ...
- 2,412
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 ...
- 869
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 ...
- 20.8k
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 ...
- 13.6k
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 ...
- 13.6k
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 ...
- 1,661
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 ...
- 539
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:
...
- 9,407
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 ...
- 170
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 ...
- 211
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 ...
- 201
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, ...
- 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 ...
- 967
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 ...
- 5,376
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?
...
- 943
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 ...
- 20.8k
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; ...
- 271
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 ...
- 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 ...
- 2,217
5
votes
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(...)))....
- 2,412
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 ...
- 941
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 <...
- 2,595
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 (...
- 233
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 ...
- 1,155
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):
...
- 131
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.
...
- 131
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 ...
- 539
3
votes
Extending Hindley Milner with (mutual) recursion
Yes, and this is essentially what OCaml does, actually.
- 221
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 ...
- 1,027
Only top scored, non community-wiki answers of a minimum length are eligible