# Questions tagged [recursive-algorithms]

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

1,239 questions
Filter by
Sorted by
Tagged with
1 vote
15 views

### Non-recursive algorithm with exponential running time

It is well-known, that there are many recursive algorithms running in exponential time, e.g. branching algorithm, backtracking etc. . My question is, is it possible to construct a non-recursive ...
30 views

### Getting rid of asymptotic notation in Recurrence Relations

Let's suppose I want to resolve the following Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases}$$ I want to prove that ...
25 views

### Is it possible to obtain rotation or transposition with following rules?

I have been trying to solve a problem in which I faced this question which I need to answer to solve my problem. Any help or suggestions or references would be helpful ? Given a sequence of length ...
69 views

61 views

53 views

### variant of tower of hanoi

I am having a really hard time coming up with the answer for the variants of tower of hanoi. So the puzzle goes like this: there are $n$ disks and $n+1$ pegs. There is also an adjacency restriction ...
96 views

### Finding the number of pairs in an array such that all the numbers between the pair are strictly less than either number in pair

Question: Suppose we have an array $A$ of size $n$ all with distinct values. We define a pair $(a,b)$ with $a < b$ if for each $a < i < b$ we have that $A[i] < \min{\{A[a], A[b]\}}$. That ...
1 vote
14 views

### Proof that a multiple recursive function generates an infinite set [closed]

if I have an example multiple recursive function like the following: $$f(x)\begin{cases}4x\ always\\\frac{x+1}{3}\ if\ mod(x+1, 3)=0\end{cases}$$ How can I proof that it generates (or it does not) a ...
34 views

### In how many ways can they be coloured so that two successive strips have different colours?

$n$ strips are to be coloured using three colours viz. red, blue and green. In how many ways can they be coloured so that no two consecutive strips are of same colour? My Attempt: Let $a_n$ be the ...
1 vote
43 views

### Proof for number of comparisons needed to find max two elements in an array

I am reading this post which explains the algorithm to compute the two maximum numbers in an array. In the second algorithm, we need to compute the number of comparisons that the algorithm makes. The ...
1 vote
47 views

### Trying to Resolve One Recursion with Two Solutions

Background: I recently answered a question about the sequence of minimum Ford circles on each successive iteration here. I then asked myself the related question about the maximum circles on each ...
35 views

### How to proof a greedy algorithm for return loans to bank

This problem was in my homework, now I'm preparing for exam but still couldn't understand it. We have $n$ loans, each loan has initial amount $R[i]$ and interest $a[i]$, and Monthly income $S.$ each ...
1 vote
69 views

### Looking for an algorithm

I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example: List of numbers: [1, ...
21 views

### Is the height of this recursive tree $\lceil \log _{2} n \rceil$?

I adapted the following code for a recursive binary cumulative sum function in Python: ...
39 views

### Recursively determine cubic spline coefficients

I am looking for a way to fit a cubic spline on previously recorded points without using matrices. The software is running on an embedded microcontroller which is low on RAM, so calculating my ...
16 views

### Divide and Conquer: Statement Explanation

I have started reading Introduction to Algorithms by Thomas H Cormen. In Chapter 4, There is sentence that says Subproblems are not necessarily constrained to being a constant fraction of the original ...
27 views

### Proposition of fast algorithm for graph with weights

If ever your Djkstra algorithms are in a situation where the max weight is much smaller than the number of vertices in your graph, try transforming each weight of size "x" into "x" ...
1 vote
101 views

62 views

### Methods and knowledge needed for the conversion of $\sum$ and $\prod$ into non-iterative expressions

I think this might be a very broad question, but here it goes. I have made a formula, using a sigma function, to give the $n$th number in a recursive sequence. I'm trying to make it into a non-...
1 vote
42 views

32 views

### Proof of monotonicty of power functions

For all $x\in\mathbb R$ and $n\in\mathbb Z,$ we define the “nth power $x^n$” recursively by $x^0=1,$ $x^{n+1}=x^n \cdot x.$ a) prove that $f(x) = x^n$ is monotonic on $(-\infty, 0]$ and $[0, \infty).$ ...
1 vote
401 views

### Why is "Turing machine makes no left move" decidable?

We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move ...
1 vote
161 views

### Decidability of DCFL and Undecidability of CFL with respect to regularity

I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and ... 21 views

### Prove that divide and conquer for max sub array problem is O(n) if logs and exp are considered elementary(take one unit of time each)

I want to show that if logarithms and exponentials are considered as elementary that the divide and conquer algorithm is O(n) instead of O(n*log(n)) for the max sub array problem. I think it has ...
23 views

### Divide and Conquer Algorithm comparison operator recursion

given a divide and conquer recursion \begin{equation} T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + N \end{equation} for $n \geq 2$ and $C_1 = 0$. I want to show that the explicit solution is ...
174 views

### Divide and Conquer Algorithm for a Grouping Problem

I am trying to understand Divide and Conquer algorithm, I learnt it through the Skyline problem and I was able to understand that quite well, however the below problem is giving me troubles. I was ...
### Find a function 𝑓(𝑛) such that $𝑡_𝑛 ∈ Θ(𝑓(𝑛))$
I have a recurrence equation which is $t_n = -\frac{21}{2} 7^n + \frac{21}{2} 5^n + 10 n \cdot 5^n$. I need to find a function $f(n)$ such that $t_n \subset \Theta(f(n))$. The problem here is ...