# Tag Info

54

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 ...

49

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 not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate ...

34

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 ...

28

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 should be called on a smaller argument. In fact, quite often tail recursive functions are designed to loop forever. For example, here's a trivial tail recursion (...

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 $\... 23 Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is$T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get$...

22

A lot of research in this area has been done, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection. A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse ...

21

The original Curry-Howard correspondence is an isomorphism between intuitionistic propositional logic and the simply-typed lambda calculus. There are, of course, other Curry-Howard-like isomorphisms; Phil Wadler famously pointed out that the double-barrelled name "Curry-Howard" predicts other double-barrelled names like "Hindley-Milner" and "Girard-Reynolds"...

19

The reason that loops are faster than recursion is easy. A loop looks like this in assembly. mov loopcounter,i dowork:/do work dec loopcounter jmp_if_not_zero dowork A single conditional jump and some bookkeeping for the loop counter. Recursion (when it isn't or cannot be optimized by the compiler) looks like this: start_subroutine: pop parameter1 pop ...

17

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 implementation-oriented toward broken implementations of function calls/recursion. Many languages implement loops via recursion, so loops are clearly not going ...

16

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 ...

14

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 vaguely defined. Also, foo might best be understood as an instance of last-call optimization with respect to single-assignment variables as the language Oz has and as discussed in Concepts, Techniques, and Models of Computer ...

13

You ask, I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$? There are many things wrong in the implied conclusion. $O(\_)$ only gives you an upper bound. The true behaviour may be of much smaller growth. Asymptotics (like $O(\_))$ only give you only something in the limit, that is you can only expect the bound to hold ...

12

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 only tail-calls. This is the CPS transform. CPS (Continuation-Passing Style) is a form of expressing code by passing each function a continuation. A ...

11

It is just an LL(1) parser implemented with recursive descent. Starts with: AdditionExpression ::= MultiplicationExpression | AdditionExpression '+' MultiplicationExpression | AdditionExpression '-' MultiplicationExpression apply left-recursion removal to get an LL(1) grammar: AdditionExpression ::= MultiplicationExpression ...

11

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 have 4 choices of neighbors for the first character and subsequent characters have only 3 or less than 3 choices but we can take it as 4 (permissible slopiness in ...

10

For numbers that are small, the binary GCD algorithm is sufficient. GMP, a well maintained and real-world tested library, will switch to a special half GCD algorithm after passing a special threshold, a generalization of Lehmer's Algorithm. Lehmer's uses matrix multiplication to improve upon the standard Euclidian algorithms. According to the docs, the ...

10

Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls. The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value ...

10

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 position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store ...

9

If by Tarski's fix point theorem you mean the Knaster–Tarski fixpoint theorem, then it's widely applicable and very general. All you need is a complete lattice and a monotone function on the lattice. There are many rather different examples of those. Tarski-Knaster is for example used in the coinductive definition of bisimilarity. Another application is to ...

9

The Curry-Howard relates type systems to logical deduction systems. Among other things, it maps: programs to proofs program evaluation to transformations on proofs inhabited types to true propositions type systems to logical deduction systems If the type system admits a Y combinator, then that means that the corresponding logical deduction system is ...

8

I'll suggest two methods, but since this is your exercise, you'll have to work out some of the details. Important: study them both. Method 1 (the dumb method) We're going to use guess-and-check. In other words, we're going to guess a solution to the recurrence $T$, and then we'll check whether our guess is correct. How do we come up with a reasonable ...

8

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 is a good example. If x, y and z are some natural numbers (or integers, or rational numbers, or real numbers, or complex numbers, or N×N matrices, or any of a ...

8

The canonical reference for this is Peter Dybjer, Inductive Families, which gives a pretty comprehensive treatment of inductive families based on eliminators.

7

My favorite way to teach recursion is by reference to the Recursion Fairy. I'm sure we're all familiar with the idea that stories can be a very effective way to teach ideas; people seem built to hear and remember stories. The Recursion Fairy is an explanation suggested by Jeff Erickson, which lends well to this approach. As Jeff E. writes: Recursion is ...

7

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 relations for sequences of numbers. You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.

7

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$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ ...

7

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., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes distance and ...

6

I suppose that each node has a pointer to its parent (unless it's the root), as well as to its first child (if any), and its child has a pointer to its next sibling (if any). You can now simulate your favorite traversal order. You just need to come up with a rule of selecting the next node. For example, suppose you want to simulate postorder. Your first node ...

6

If all you have this definition rule (which doesn't perform any computation), it won't help you. You also need a way to use this definition, like you did in your code example: you implicitly used another language construct, where a definition is available in the next line. To make things precise, I'll consider a construct which combines a definition with a ...

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