The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
21 views

Constructive ordinals and constructive isomorphisms

If well-orderings A and B have the same recursive ordinal number, is there a recursive order-preserving bijection from A to B? (This was asked on math.SE as well ...
7
votes
2answers
414 views

Are there problems for which divide-and-conquer / recursion is provably useless?

When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the ...
5
votes
1answer
76 views

Extending simple types to allow `fix`

I'm reading some lecture notes saying that “fix cannot be defined in the simply typed lambda-calculus” and that “no expression that can lead to non-terminating ...
4
votes
2answers
148 views

Higher order Quines - when do super Quines exist?

The normal Quine - a program that prints its own code - is a special case of an n-Quine. An n-Quine is a program that prints code for a different program that after n iterations of printing and ...
0
votes
1answer
266 views

Difference between a cyclic and a left-recursive context-free grammar?

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things: The original purpose of the LC transform is to allow simulation of left-corner parsing ...
2
votes
1answer
164 views

recursion schemes that prune

Probably the most common recursion scheme is the catamorphism, or fold. This is a recursion that takes a data type and "deconstructs" it into something else. For example, we can calculate the length ...
5
votes
1answer
404 views

Trampoline that automatically balances heap and stack

While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course ...
5
votes
2answers
237 views

Does “Productive function” mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is ...
4
votes
2answers
206 views

Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states: We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
2
votes
0answers
100 views

Recursion Schemes for Static Analysis (AST)

In the process of creating an AST analysis framework one of the challenges is creating good reusable functions and to avoid too much boiler-plate code. To that end catamorphisms seem like a good fit, ...
9
votes
6answers
2k views

Removing recursion - a look into theory behind the scenes

I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make ...
3
votes
2answers
974 views

Stack memory usage for tail calls

I'm puzzled by this statement from Wikipedia: For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack ...
5
votes
1answer
352 views

Parallel solution of recurrence equation

One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the ...
9
votes
3answers
862 views

About recursion

Where did the idea of recursion originated from? I mean first who thought about it.Can anybody care to explain about the origin of recursion and subsequent impact on the computer science?