# Questions tagged [recursion]

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

431 questions
Filter by
Sorted by
Tagged with
2k views

### Towers of Hanoi but with arbitrary initial and final configuration

Recently, I came across this problem, a variation of towers of hanoi. Problem statement: Consider the folowing variation of the well know problem Towers of Hanoi: We are given $n$ towers ...
109 views

### Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
710 views

### Proving correctness of the algorithm for convex polygon minimum cost triangulation

I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
161 views

### Can a recurrence relation be translated to a composite function of itself?

Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions. Having as an example this ...
32 views

### The use of master theorem appriopriately [duplicate]

I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is: $T(n) = 3T(n/5) + n^{0.5}$ Can I use the master theorem in that relation? If so, can I say that ...
843 views

### Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $T(n) = 2T(\frac{n}{2}) + \log_{2}n$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: ...
1k views

### Tasks in which recursion is either the fastest or only way to produce a result [duplicate]

I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be ...
641 views

### Why does backtracking work the way it does?

I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking ...
175 views

### A Formula For Generalized Josephus problem

There is a formula in wikipedia for the general case of josepus problem Josephus Problem But there is no reference for it, I don't know where it came from and I need too find out... Maybe Donald ...
309 views

### Prove $\varphi(x)$ to be primitive recursive

Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive. In proving $\varphi$ to be a p.r. function I think it could come in handy the ...
314 views

8k views

60k views

### What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...
44k views

### When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
3k views

### Examples of sophisticated recursive algorithms

I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend. The recursion in this algorithm (while being very simple) is quite sophisticated. ...