49
votes
Accepted
Will this program terminate for every Integer?
The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does ...
48
votes
Accepted
Why is tail recursion better than regular recursion?
if that is the only reason, why the compiler would not be able to optimize the regular recursive call?
You are focusing on the wrong thing here: the reason the optimization works is because of the ...
- 6,683
28
votes
Accepted
Difference between Tail-Recursion and structural recursion
Structural recursion: recursive calls are made on structurally smaller arguments.
Tail recursion: the recursive call is the last thing that happens.
There is no requirement that the tail recursion ...
- 31.8k
21
votes
Accepted
Is the Berkeley tutorial on Fibonacci trees using wrong figures?
I would like to say both you and that Berkeley tutorial are correct.
As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the ...
- 39.2k
16
votes
Accepted
What's the Big O runtime of a DFS word search through a matrix?
The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string.
When we start searching from a character we ...
- 1,215
15
votes
Accepted
What property of cons allows elimination of tail recursion modulo cons?
While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use pow to illustrate since you're foo is so ...
- 12.2k
13
votes
Why is tail recursion better than regular recursion?
The way a standard function/procedure (from now on I'll just say "function") call works is that the caller needs to store onto the stack whatever state it needs for computations that occur ...
- 24.9k
12
votes
Accepted
Count total number of k length paths in a tree
This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th ...
- 1,131
9
votes
What property of cons allows elimination of tail recursion modulo cons?
I’m going to beat around the bush for a while, but there is a point.
Semigroups
The answer is, the associative property of the binary reduction operation.
That’s pretty abstract, but multiplication ...
- 1,250
8
votes
Accepted
How to derive dependently typed eliminators?
The canonical reference for this is Peter Dybjer, Inductive Families, which gives a pretty comprehensive treatment of inductive families based on eliminators.
- 8,437
8
votes
Accepted
Worst-case input for median-of-medians with groups of size 3
Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in [1] (while they proposed a variant running in linear time). I checked some follow-...
- 7,623
8
votes
Accepted
Why we can not define factorial in lambda calculus
The language doesn't really allow definitions of the form $\text{name}=\textit{expr}$. That's just a shorthand for readability. All of these definitions have to be eliminated by substitution to get a ...
- 2,586
7
votes
Is the Berkeley tutorial on Fibonacci trees using wrong figures?
Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), ...
- 440
7
votes
Why we can not define factorial in lambda calculus
$\lambda$-calculus has a very restricted set of symbols. You can't refer to a a $\lambda$-term by a variable name. You can't refer to something by itself in the definition because there is no way to &...
- 374
6
votes
How to derive dependently typed eliminators?
You might find some of our recent papers on this useful, as we derive eliminators for lambda-encoded datatypes. For example, see this one for generic derivation of eliminators, and this one for the ...
- 61
6
votes
Is there any recursive function f whose code is unique?
No. The Padding Lemma states that there is a primitive recursive function $\sf pad$ such that, if $n$ is a code for $f$, then ${\sf pad}(n)$ is another code for $f$ which is larger than $n$.
...
- 14.7k
6
votes
Accepted
How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?
Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.
For ...
- 281k
6
votes
Accepted
Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model ...
- 30.4k
6
votes
Accepted
Can the minimisation operation be seen from a programming language perspective?
Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages?
Yes, ...
- 246
5
votes
Accepted
Alan Perlis Epigram on Recursion
I can't presume to speak for Perlis, but my intuition is as follows:
Recursion is descriptive
Especially at the time this was written, the specification of a recursive function seems much more ...
- 8,437
5
votes
Will this program terminate for every Integer?
If we look at this in terms of the C language, an implementation is free to replace code with code that produces the same result in all cases where the original doesn't invoke undefined behaviour. So ...
- 32.6k
5
votes
Accepted
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so
$$
g(n) \geq \...
- 281k
5
votes
Accepted
Explanation of O(n2^n) time complexity for powerset generation
Observe that:
$T(N) = 2T(N-1) + 2^{N-1}$
$T(1) = 2$
Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that ...
- 166
5
votes
Accepted
What does the phrase "Simple For Loops" mean in computability theory?
The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:
...
- 281k
5
votes
Accepted
Any reason why Turing Machine would prevail on recursion theory?
With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.
5
votes
Accepted
How does primitive recursion handle mutual recursion?
Suppose you have two mutually recursive maps $f, g :
\mathbb{N} \to \mathbb{N}$ defined by
\begin{align*}
f(n) &= \Phi(f, g, n), \\
g(n) &= \Psi(f, g, n)
\end{align*}
We may replace this ...
- 31.8k
5
votes
Are recursive Horn clauses first order?
Horn clauses in prolog are not recursive definitions. They are logical formulas. For example,
times(_, 0, 0).
times(x, S(y), w) :- times(x,y,z), plus(x,z,w).
is ...
- 31.8k
4
votes
What is the time complexity of this binomial coefficient algorithm?
The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.
Now prove it.
- 24.9k
4
votes
Accepted
Why is recursive programming problematic for branch predictors
It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -> return 1 else return n * ...
- 32.6k
Only top scored, non community-wiki answers of a minimum length are eligible