# Tag Info

51

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 finite amount of memory, the computation has a finite number of possible steps, so it's possible to simulate them all with a finite automaton. Having unbounded ...

32

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. Moreover, many Turing-complete models of computation have no recursion, for example Turing machines and counter machines. Primitive recursive functions correspond to ...

25

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 stack $s$ of integers. Such a stack has two modifying operations, $\DeclareMathOperator{\push}{push}\push(s, x)$ (which puts a new element $x$ on the stack) and $\... 15 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 a new stack frame (for the new invocation of the recursive function), and returning removes a stack frame (for the just-completed innovation of the recursive ... 6 First of all, there is a known formula that gives the correct answer in this case: if$a,b$are relatively prime, then the maximal element which cannot be written as a non-negative combination of$a,b$is$(a-1)(b-1)-1$. (Extending this to the case where$a,b$are not relatively prime is a nice exercise.) Second, suppose you don't know this formula, and ... 4 The idea is to split the sum into two parts: For individual values of i for$i <= a^{1/2}$, then for individual values of floor (a/i). For example find the smallest and largest values i where floor (a/i) = 1 or 1 <= a/i < 2. The values i^2 can be summed with a simple formula. Here's how we can do this efficiently: We have$a/i ≥ k$iff$i ≤ a/k$... 4 Let$S_i$be the sum of the array upto index$i$. Then we can directly calculate the sum of any contiguous subarray$x_i, x_{i+1}, ..., x_{j}$using the expression$S_j - S_{i-1}$. This subarray will have even sum only if$S_{i-1}$and$S_j$are both even or both odd. With this in mind, we can count how many even and odd$S_i$we have and then calculate ... 3 Instead of constructing a regular expression, it is better to construct a DFA, or rather, a DFA with some "missing transitions". The DFA has the following states:$q_0$: initial state.$q_A$: state after seeing one A.$q_B$: state after seeing one B.$q_{BB}$: state after seeing two Bs. The transition function is$$\begin{array}{c|cccc} & q_0 & ... 2 As far as I can tell, and in my own experience, you can implement any recursion as an iteration. As mentioned above, recursion uses the stack, which is conceptually unlimited, but practically limited (have you ever gotten a stack overflow message?). In my early days of programming (in the third quarter of the last century of the last millennium) I was ... 2 A straightforward answer would be "iteration", since recursion consumes stack memory and imposes computational overhead for calling functions. However, in practice both implementations can be equivalent at machine code level due to compiler optimizations (such as tail call optimization). In general, you shouldn't really be concerned about these matters ... 2 Contrary to what you (and many people) may think, in the field of programming languages, the most primitive control-flow operation is actually pattern matching! With a simple type system (say the simply-typed lambda calculus) plus unit types and sum types, you can encode the boolean type easily. Let$\mathbf{1}$be the unit type. The boolean type is simply$...

1

This is perhaps most clear at the assembly level. There is an instruction pointer, which normally moves to the next instruction after executing the current one. Any instruction that interferes with that behavior is, by definition, a control flow instruction. Conversely, if no instruction can have an effect to alter the instruction pointer, the program has ...

1

Let Nums be the value of the array after method execution, and nums the initial value. Let, P(i) = Nums[0..i-1] is the same as nums[0..i-1], but ignoring val. Your algorithm is correct if P(nums.length) is true. This can be shown by realising that P is true at the beginning of the loop, and each iteration of the loop preserves P. Initially, i = 0 in the ...

1

You have to perform a visit of the directory graph, such as a DFS. Since the graph you're dealing with is a tree, you can use a tree traversal instead, which is conceptually identical but should be easier to implement. Just a pedantic note: you don't need the Church thesis to say that every recursive function is Turing-computable, it can be proven formally.

1

Since deleting or inserting in the middle of a vector is a linear time operation, a linked list is the better choice. This assumes of course that you have reasonably large lists (i.e. they don't fit in cache) and that you frequently insert or delete items in the middle, compared to just iterating or changing the end of the list. If you have small lists or ...

1

Well, if you're looking for easiness of operations, I would recommend a vector. Vectors support a wide array of operations, providing a large number of top-level methods, and iterators namely std::iterator, reverse iterator, and a lot more. With these top-level functions and iterators however, comes the caveat of not being able to modify these to suit your ...

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