Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
55 votes
Accepted

Iteration can replace Recursion?

It's possible to replace recursion by iteration plus unbounded memory. If you only have iteration (say, while loops) and a finite amount of memory, then all you have is a finite automaton. With a ...
Gilles 'SO- stop being evil''s user avatar
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 ...
Gilles 'SO- stop being evil''s user avatar
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 ...
Jörg W Mittag's user avatar
35 votes

Iteration can replace Recursion?

Every recursion can be converted to iteration, as witnessed by your CPU, which executes arbitrary programs using a fetch-execute infinite iteration. This is a form of the Böhm-Jacopini theorem. ...
Yuval Filmus's user avatar
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 ...
Andrej Bauer's user avatar
  • 30.5k
26 votes

Iteration can replace Recursion?

As an example to the answer from Gilles, here is an "iterative" algorithm for the Ackermann function (using the common Ackermann-Péter version mentioned by Wikipedia $a(n,m)$). We need a ...
Paŭlo Ebermann's user avatar
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 ...
John L.'s user avatar
  • 39k
19 votes
Accepted

Why are loops faster than recursion?

The reason that loops are faster than recursion is easy. A loop looks like this in assembly. ...
Johan's user avatar
  • 1,080
17 votes

Why are loops faster than recursion?

These other answers are somewhat misleading. I agree that they state implementation details that can explain this disparity, but they overstate the case. As correctly suggested by jmite, they are ...
Derek Elkins left SE's user avatar
16 votes

Iteration can replace Recursion?

There are already some great answers (which I can't even hope to compete with), but I'd like to pitch this simple explanation. Recursion is just the manipulation of the runtime stack. Recursing adds ...
Alexander's user avatar
  • 516
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 ...
Navjot Singh's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
13 votes
Accepted

Is this a generic way to convert any recursive procedure to tail-recursion?

Your description of your algorithm is really too vague to evaluate it at this point. But, here are some things to consider. CPS In fact, there is a way to transform any code into a form that uses ...
Nathan Davis's user avatar
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 ...
Pseudonym's user avatar
  • 22.2k
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 ...
Antti Röyskö's user avatar
11 votes

Correct name for a recursive descent parser that uses loops to handle left recursion?

It is just an LL(1) parser implemented with recursive descent. Starts with: ...
AProgrammer's user avatar
  • 3,069
9 votes

Can Breadth-First Search be Implemented Recursively without Data Structures?

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity. Embedded-Queue Cheating If you look at virtually any description of BFS, e.g.,...
Ami Tavory's user avatar
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 ...
Davislor's user avatar
  • 1,241
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.
cody's user avatar
  • 8,233
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-...
xskxzr's user avatar
  • 7,455
7 votes

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

Typically, by writing a recurrence relation for the running time and then solving the recurrence relation. See How to come up with the runtime of algorithms? and Solving or approximating recurrence ...
D.W.'s user avatar
  • 160k
7 votes
Accepted

Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a total of $d$ drops of these eggs (rather than $d$ ...
Rick Decker's user avatar
  • 14.8k
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), ...
JounceCracklePop's user avatar
6 votes
Accepted

Efficient algorithm for getting from 1 to n with 3 specific operations

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will ...
David Richerby's user avatar
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 ...
Aaron Stump's user avatar
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$. ...
chi's user avatar
  • 14.6k
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 ...
Yuval Filmus's user avatar
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 ...
Joey Eremondi's user avatar
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, ...
confusedcius's user avatar
5 votes

How does recursion works when there are 2 or more consecutive recursive calls?

Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other. However, since the two recursive calls operate on disjoint sections of the ...
David Richerby's user avatar

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