Questions tagged [recursion]
For questions relating to recursion, or functions that call themselves.
11 questions
9
votes
2
answers
489
views
Can total (primitive) corecursion be implemented?
I'm trying to understand how to implement corecursion in a total functional context. I've already implemented recursion using standard techniques (for loops) but I ...
- 901
9
votes
7
answers
2k
views
Is there a generic way to refer to the current function in recursion?
In writing recursive functions (functional style), I often need to refer to the current function (depending on the context).
e.g.
f 0 = 0
f (S n) = f n + 2
Are ...
- 467
1
vote
2
answers
2k
views
Does x86 assembly support linguistic recursion? [closed]
In my book "Jezici za gimnazijalce" (not available online) and in my Bachelor thesis (which will be online in about a month) I was claiming that assembly languages are like the Piraha ...
- 2,337
15
votes
1
answer
440
views
Extending Hindley Milner with (mutual) recursion
What's a good approach for extending Hindley Milner with mutual recursion without de-sugaring to let+fix+records?
My thinking is (assuming no polymorphic recursion)
Collect mutually recursive lets ...
- 251
7
votes
2
answers
2k
views
Dynamic and Static scoping and recursion
So I learned the concept of lexical and dynamic scoping in programming languages. But I am not quite sure about the behaviour of these concepts in recursion(or even not recursion, but two different ...
- 73
19
votes
6
answers
4k
views
What is the use of explicitly specifying if a function is recursive or not?
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 ...
- 695
3
votes
1
answer
517
views
X86-64 Assembly for Recursive Functions
A compiler I'm writing generates the following x86-64 assembly (AT&T syntax) for a recursive factorial function. I convert the assembly into an ELF executable using ...
8
votes
2
answers
504
views
How to optimize non-tail recursion?
Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: tail call optimization applies.
However, this doesn't apply to ...
- 9,672
17
votes
1
answer
1k
views
How can we define a denotational semantics for recursive functions?
Motivation
I want to define a denotational semantics (see here or here) for recursive functions in my language, by representing them as mathematical functions.
Background
Consider a simple language ...
- 2,532
12
votes
6
answers
3k
views
Early binding, mutual recursion, closures. Can I have all three?
Take this Python snippet of two functions that are mutually recursive and form closures:
...
- 1,491
16
votes
3
answers
594
views
What are the trade-offs in supporting Tail Recursion Optimization, but not Tail Call Optimization?
Tail Call Optimization allows a function call as the returned value of a function to be optimized to a goto, preventing the stack from growing. Among other things, ...
- 4,870