60

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


53

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


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


20

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


18

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

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


16

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


16

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


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


13

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


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


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

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


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

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


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.


8

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


7

As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways: Bartek's suggestion: Use an array to store all the entries computed so far. You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time. Use matrix powering. There are ...


7

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though. Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $...


7

Goldbach's conjecture is either true or false. Do a case analysis on the two possibilities. In one case, $f(x)=x$, which is primitive recursive. In the other case, $f(x)=0$, which is also primitive recursive. Therefore $f$ is primitive recursive.


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