# Tagged Questions

The tag has no usage guidance.

92 views

### What is the relationship between tail recursion with other recursions? [closed]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
76 views

### Growth rate of primitive recursive functions

Pardon me for asking a question whose answer is surely well-known, but is beyond my expertise: Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential $O(c^n)$...
40 views

### Omitting parameters in primitive recursive functions

will replacing the usual schema of primitive recursion: $$f(0,\vec x) = c (\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x), n, \vec x)$$ by the form:  f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec ...
55 views

### How can I find tight asymptotic bounds for this half-history recurrence relation?

The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$. Fairly simple tree analysis shows that \$T(n)\...
486 views

### Program reasoning about own source code

The inspiration for this question is the following (vague) question: What are the programming language/logical foundations for having an AI which could reason about its own source code and modify it? ...
128 views

### Is there a closed form equation for the back-propagation equation update in Neural Networks?

I was trying to understand if there was a way to express the back-propagation equations from neural networks in a better way as to understand them better. I believe the equations can be written in a ...
637 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 ...
88 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 ...
161 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 ...
542 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 ...
176 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 ...
809 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 ...
301 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 ...
227 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 ...
110 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, ...
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 ...
1k 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 ...