# Tag Info

52

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive: int g(...

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

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

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

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 $\... 24 The solutions to some problems are more naturally expressed using recursion. For example, assume that you have a tree data structure with two kinds of nodes: leaves, which store an integer value; and branches, which have a left and right subtree in their fields. Assume that the leaves are ordered, so that the lowest value is in the leftmost leaf. Suppose ... 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$...

21

Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call: $$\begin{gather*} a_{i+1} = b_i \\ b_{i+1} = a_i \mathbin{\mathrm{mod}... 20 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"... 18 I have taught C++ to undergraduates for about two years and covered recursion. From my experience, your question and feelings are very common. At an extreme, some students see recursion as difficult to understand while others want to use it for pretty much everything. I think Dave sums it up well: use it where it is appropriate. That is, use it when it ... 16 A lot of research in this area has been dome, 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 a tree ... 16 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 ... 15 My favorite recurrence shows up in output-sensitive algorithms for computing convex hulls, first by Kirkpatrick and Seidel, but later repeated by others. Let T(n,h) denote the time to compute the convex hull of n points in the plane, when the convex hull has h vertices. (The value of h is not known in advance, aside from the trivial bound h\le n.)... 15 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 ... 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 ... 14 What works If you nest the definition of the fixpoint on lists inside the definition of the fixpoint on trees, the result is well-typed. This is a general principle when you have nested recursion in an inductive type, i.e. when the recursion goes through a constructor like list. Fixpoint size (t : LTree) : nat := let size_l := (fix size_l (l : list LTree)... 13 My answer is based on the explanation given in the book Structure and Interpretation of Computer Programs. I highly recommend this book to computer scientists. Approach A: Linear Recursive Process (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) The shape of the process for Approach A looks like this: (factorial 5) (* 5 (factorial 4)) ... 13 Simply said, tail recursion is a recursion where the compiler could replace the recursive call with a "goto" command, so the compiled version will not have to increase the stack depth. Sometimes designing a tail-recursive function requires you need to create a helper function with additional parameters. For example, this is not a tail-recursive function: ... 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 The recursion that I used in my paper "A linear-time algorithm for computing the Voronoi diagram of a convex polygon" by Aggarwal et al is also quite complicated. Here is a description of the algorithm from our paper. In case it's not clear from the description, in step 3 the red points are partitioned into crimson and garnet points. Steps 1, 3, and 6 are ... 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 ... 12 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 ... 11 From someone who practically lives in recursion I will try and shed some light on the subject. When first introduced to recursion you learn that it is a function that calls itself and is basically demonstrated with algorithms such as tree traversal. Later you find that it is used a lot in functional programming for languages such as LISP and F#. With the F# ... 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 ... 10 From what you wrote it seems that for all k you have T(k)=k-1+T(k-1) and T(1)=0. Therefore you can get it directly:$$T(n)=(n-1)+(n-2)+\dots+1+0 = \sum_{k=1}^{n}{(k-1)}=\frac{n(n-1)}{2} So $T(n)$ is in $Θ(n^2)$.

10

As others have already indicated in comments, you really have two unrelated functions here: testing whether the tree is a search tree, and counting the complete branches. Unless the assignment specifically calls for it, I would write two separate functions. Let's see abount counting the complete branches first. That means counting the nodes that have both a ...

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

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

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