# Tag Info

## Hot answers tagged recursion

Accepted

### Program reasoning about own source code

I think you are asking about two different things. The ability of a programming language to represent all its programs as data. Reasoning about programs as data. For analytical purposes it's ...
• 10.3k
Accepted

### Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$ To see the lower bound, apply the recurrence definition $\log n$ ...
• 1,101
Accepted

### Growth rate of primitive recursive functions

The answer is no, there is no exponential bound on PR. PR contains Knuth's up-arrow functions, Elementary functions, etc. PR is equal to the union of Grzegorczyk hierarchy. Exponential functions ...
• 21.3k
Accepted

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

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime? Yes. Note that if a tally language has “recursive algorithm” with polynomial “recursive ...
• 16.3k

### Conservative Approximation of Kleene-Mycroft Iteration for Polymorphic Recursion?

You should have a look at the following paper -- and the previous work by Gori and Levi: On Polymorphic Recursion, Type Systems, and Abstract Interpretation Marco Comini, Ferruccio Damiani, Samuel ...
• 1,910
Accepted

### Termination checking for Scott-encodings in System F with positive-recursive types

I'll first point you to Types for the Scott Numerals by Plotkin, Cardelli and Abadi, where they show how to encode Scott numerals in plain old system F. This at least shows that you can write the "...
• 13.2k

### Program reasoning about own source code

No there is no current system that does all four steps in your system. If you want to design a system one of the first requirements is homoiconic language. At minimum you would want your core ...
• 1,631

### Program reasoning about own source code

As @user217281728's answer mentions there are a type of machines related more to inference and AI, called Gödel Machines A Gödel machine is a self-improving computer program invented by Jürgen ...
• 571

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

From the point of view of lambda-calculus "tail call optimization" means take a CPS converted version the program, and eta-reduce continuations of the form $\lambda x. k\;x$ to $k$ Since eta-...
• 31.7k

### Termination checking for Scott-encodings in System F with positive-recursive types

(Sorry for the blatant self-advertisement that follows!) In addition to what was already said, you should really check out our recent TOPLAS paper (https://doi.org/10.1145/3285955), which deals with ...

### History of recursion

From Recursive Functions article on SEP: The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of ...
• 21.3k

### History of recursion

Maybe slightly tangential to the original question, but the blog entry "How recursion got into programming: a comedy of errors" describes an interesting part of early computing history.
• 10.3k

### Program reasoning about own source code

This paper by Jurgen Schmidthuber might be of interest: http://arxiv.org/pdf/cs/0309048.pdf

### Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

There's actually two questions here! The transformation you ask about is called the tupling transformation. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be ...
• 31.7k
Accepted

### Linear regression as a hylomorphism

You can indeed see linear regression as arising from a fixed point computation, but it is better to think of it as related to transitive closure computations than to folds or unfolds. Regression is ...
• 31.7k
Accepted

### Time complexity for multiplying two lower triangular matrices

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can ...
• 141
Accepted

### Why can a Predictive Parser contain E' -> TE' | ε

... is not valid since we have "left recursion" (a variable that calls itself). That's not what a left recursion is. That's simply recursion. Direct left recursion is when a rule $A \to A\alpha$ ...
• 690

### Definitional equality of recursive function definition by "infinite unfolding"

Your predd2 is not a fixpoint; you could replace the Fixpoint by Definition. And the fact ...
• 521
1 vote
Accepted

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

It is $n^{\Theta(\log n)}$, although I'm not sure exactly what the constant in the theta is. For the upper bound (the one you already have), note that, even without the $n^2$ term but with a base case ...
• 50.3k

Only top scored, non community-wiki answers of a minimum length are eligible