# Questions tagged [recursion]

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

384 questions
Filter by
Sorted by
Tagged with
703 views

### Partial recursive function and Turing machine

The wikipedia article about primitive recursion states that An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine. My question is how ...
1k views

### Register Machine code for Fibonacci Numbers

I am not sure whether this is the right place to ask this question. I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth ...
2k views

### Particularly Tricky Recurrence Relation (Master's Theorem)

Master's theorem is shown below, The recursive function to be solved is shown below, I understand that a refers to the number of recursive calls in this function (...
1k 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 ...
107 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.
703 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 ...
156 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 ...
831 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 ...
638 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 ...
165 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 ...
293 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 ...
308 views

8k views

58k 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,...
42k 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. ...