Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
Questions tagged [recursive-algorithms]
1345 questions
9
votes
1 answer
Recursion tree T(n) = T(n/3) + T(2n/3) + cn
I have a task:
Explain that by using recursion tree that solution for:
$T(n)=T(\frac n3)+T(\frac {2n}{3})+cn$
Where c is constance, is $\Omega(n\lg n)$
My solution:
Recursion tree for $T(n)=T(\frac n3)+T(\frac {2n}{3})+cn$
Shortest path will be…
user209163
- 111
6
votes
1 answer
Applying a Math Formula in a more elegant way (maybe a recursive call would do the trick)
This is my first post in Math section. I've been redirected here from StackOverflow, users from there suggested me to ask here.
This could appear a little bit complex at first sight but afterall there's nothing special.
We are in a poker touranment,…
KingBOB
- 434
6
votes
2 answers
Characteristic equation. What is it?
Consider a recursive equation:
$$ a_n = A a_ {n-1} + Ba_ {n-2} $$
And for this type of equation, there is characteristic equation:
$ x ^ 2 = Ax + B $.
What does exactly means that this equation is characteristic? These equations are based on a…
user180834
- 1,453
5
votes
2 answers
Has anything useful come from Ackermann's Function?
Here is the function:
if (m == 0)
return n + 1;
else if (n == 0)
return A(m-1, 1);
else
return A(m-1, A(m, n-1));
This seems like an interesting function, especially since its values grow quite rapidly (my computer crashes if I try to…
user63985
5
votes
2 answers
Proof by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$
How to prove by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$?
I've tried the following and got stuck
$$
\begin{align}
T(n) &= T(n - 1) + \Theta(n) \\
&= d(n - 1)^2 + cn \\
&= d(n^2 - 2n + 1) + cn…
Peter
- 267
5
votes
0 answers
Can it be determined if this recursively defined function is a one-to-one correspondence?
I'm writing a compiler in Java and needed a gensym function. I decided that I would just try to generate unique 64 bit integers and convert them to base 36 strings. I jotted down a recursively defined function to generate the sequence. When I tested…
James Bolden
- 51
5
votes
1 answer
How to find an explicit formula for a recursive function?
Define
$$ S_{n+1} = \frac{S_n^2+x}{2S_n}$$ and $S_1 = k$, where x,k > 0.
find an explicit formula for $S_n$ in terms of n.
I don't even know where to begin. I tried using algebraic manipulation to rid of $S_{n+1}$ but nothing is working.…
Adam Staples
- 967
4
votes
1 answer
A question about a very slowly growing recursive function and whether it can provide context to very large numbers.
Let $g(x)$ be the number of digits in the base 10 representation of $x$.
I define $f(x)$, the slow growing function in question, as the following process:
Take any starting number $x$ and calculate $g(x)$. Then, plug the resulting number back into…
joshblech
- 41
4
votes
1 answer
Stepping through the Josephus problem
I'm trying to figure out how the math in the Josephus problem works exactly. I first heard of it for programming purposes so that's where my focus has been. The formula does seem to be recursive from what I can tell, and that's what's been killing…
Jossie B
- 43
3
votes
1 answer
Minimum radius cirlce problem
Given $n$ points in 2D plane .Find the minimum radius of the circle which contains at least $k$ points ($k\leq n$)? The points can be in or on the circumference of the circle.
I tried the recursion approach; i.e, if $C(i)$ is the circle with $i$…
Ayush Goyal
- 141
- 4
3
votes
2 answers
Towers of Hanoi Starting From Initial (Legal) Configuration?
I was recently asked in an interview how an algorithm for solving the classic Towers of Hanoi problem would differ if you were given an initial (legal) configuration of the towers, and had to start from there - in the middle so to speak. I could not…
Rome_Leader
- 381
2
votes
1 answer
How to solve the recursive complexity?
I have such recursive complexity $T(n) = T(n-2) + log(n)$. The problem is that I cant use a recursion tree or the master theorem. The only way, which I know, is to guess and then proof the answer.
Any ideas?
Rocketq
- 123
2
votes
2 answers
Master theorem, algorithms $T(n) = 2T(n/3) + \log n$
Can I solve $ T(n) = 2T(n/3) + \log n $ using the master theorem?It doesn't seem to fit in any case.
user142810
- 23
2
votes
1 answer
Recursion with non-equal exponents
This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this question here ...
I'm looking for a general way…
sorush-r
- 133
2
votes
2 answers
Do all recursive fuctions also have a non-recursive version of itself?
Is there any proof that states that any recursive function has to have a non-recursive function that has the same output as the recursive function?
TheKobra
- 155