# Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

380 questions
Filter by
Sorted by
Tagged with
164 views

175 views

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

The question: Given those 3 valid operations over numbers and an integer $n$: add $1$ to the number multiply the number by $2$ multiply the number by $3$ describe an efficient ...
81 views

### Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
443 views

### Side effect and recursion

My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure". Anyway I don't understand why, even because I find side-...
677 views

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

I was learning about recursion and i came across the following pseudo code for quicksort. ...
46 views

### Axiomatisation in the presence of recursion

I read Klaus Havelund's thesis on the Fork Calculus: http://havelund.com/Publications/thesis.ps He develops the Fork calculus for reasoning about concurrent functional programs, the motivation being ...
28 views

### T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(log n)? [duplicate]

how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(logn)? or T(n)=T(n-1)+T(n-3)+1 the same.. when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`.. it's a Q about AVL-2 tree,the same rules of AVL tree ...
62 views

### Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
88 views

### What Exactly is “Improvement” in Seed AI?

From LessWrongWiki, a seed AI [I]mproves itself by recursively rewriting its own source code without human intervention. Some would even say this could bring about an Intelligence Explosion. Many ...
11k views

### Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
602 views

### What is the formal justification for the correctness of the second formulation of rod cutting DP solution

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference. Define $r_j$ to be the optimal way to cut a rod ...
12k views

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

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
229 views

17k views

### How to calculate the mergesort time complexity?

Recently while reading a book (Skienna) I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of ...
204 views

### Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

Here is pseudocode for the algorithm: ...
I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...