The 2024 Developer Survey results are live! See the results

Questions tagged [recursion]

The tag has no usage guidance.

37 questions
Filter by
Sorted by
Tagged with
785 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? ...
• 638
5k views

History of recursion

Who introduced the idea of recursion? Can someone explain where it came from and how it impacted computer science?
451 views

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

How can I solve the following recurrence relation? $$f(n) = f(n-1) + f(n - \log n)$$
• 1,101
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

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 ...
• 2,294
230 views

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

This is what I'm looking for. Take a recursive algorithm: def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) and turn it into ...
• 323
424 views

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

Is there any research on termination analysis on Scott-encodings in System F with positive-recursive types. All papers I have found use languages with constructors and case analysis (for example ...
• 701
244 views

What are considered to be the most canonical and important consequences of the recursion theorem?

The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a ...
• 29.3k
449 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 ...
• 163
2k 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 ...
169 views

• 119
Applying $/mu$-Operator for Unbounded minimization
I'm learning how to use the $\mu$-Operator for unbounded minimization and trying to define a partial recursive function $g(y,z)$ from the primitive recursive function $f$ defined as:  f(x, y, z) = ...