Questions tagged [recursion]

For questions relating to recursion, or functions that call themselves.

Filter by
Sorted by
Tagged with
20 votes
6 answers

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 ...
a coder's user avatar
  • 685
15 votes
3 answers

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, ...
Rydwolf Programs's user avatar
15 votes
1 answer

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 ...
David Young's user avatar
  • 2,127
12 votes
6 answers

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

Take this Python snippet of two functions that are mutually recursive and form closures: ...
BoppreH's user avatar
  • 1,441
9 votes
0 answers

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 ...
aindurti's user avatar
  • 191
8 votes
7 answers

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 ...
tinlyx's user avatar
  • 417
8 votes
2 answers

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 ...
Bbrk24's user avatar
  • 8,907
8 votes
1 answer

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 ...
Corbin's user avatar
  • 841
7 votes
2 answers

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 ...
poiug07's user avatar
  • 73
3 votes
1 answer

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 ...
Veera Sivarajan's user avatar
1 vote
2 answers

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 ...
FlatAssembler's user avatar