Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
357
questions with no upvoted or accepted answers
7
votes
0
answers
386
views
Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?
The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc.
I have a function ...
- 1,580
6
votes
0
answers
310
views
Simple recursive algorithms to manually compute elementary functions with pocket calculators
Let $x_n\,(n\in\Bbb N)$ be the sequence defined by
$$x_{n+1}=\frac{x_n}{\sqrt{x_n^2+1}+1}\tag 1$$
then it's well know that $2^nx_n\xrightarrow{n\to\infty}\arctan(x_0)$.
This gives a very simple ...
- 16.1k
6
votes
0
answers
178
views
Recursive induction proof
$$π‘(π) = (πβ1)+\frac{πβ1}{π^2}β
\sum_{k=1}^{n-1}t(k)$$
Use induction to prove that $π‘(π)β€2π$ for all $πβ₯1$.
I have the base case.
I got \begin{align} π‘(m+1) & = m+\frac{m}{(m+1)^2}β
\...
6
votes
0
answers
276
views
Generating Functions, Recursive Polynomials
At the CMFT international conference in Turkey (2009), the following open problem was given:
Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
- 3,251
6
votes
0
answers
2k
views
When do ο¬oors and ceilings matter while solving recurrences?
I came across places where floors and ceilings are neglected while solving recurrences.
Example from CLRS (chapter 4, pg.83) where floor is neglected:
Here (pg.2, exercise 4.1β1) is an example where ...
- 193
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
5
votes
0
answers
102
views
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 ...
- 51
5
votes
0
answers
325
views
Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?
For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $ \small z^2 $ by ...
- 35k
4
votes
0
answers
40
views
Construct following semidecidable sets
Being an undergrad, was looking through our previous year task books during exam preparation and got stuck on this one:
Are there such semidecidable (recursively enumerable) sets X, Y that their ...
- 336
4
votes
0
answers
140
views
What's the next "recursion" here?
Plotting a single 3d helix is
x = cos(t);
y = sin(t);
z = t;
From this equation:
x = [R + a cos(\omega t)] cos t
y = [R + a cos(\omega t)] sin t
z = h t + a sin(omega t)
Comes the awesome helix-...
- 153
4
votes
0
answers
797
views
Algorithm for reversion of power series?
Given a function $f(x)$ of the form:
$$f(x) = x/(a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+a_5x^5+...a_nx^n)$$
Let $A$ be an arbitrary (any) infinite lower triangular matrix with ones in the diagonal:
$$A ...
- 7,446
4
votes
0
answers
295
views
Recursive Sequence from Finite Sequences
I'm searching for the name of these kind of sequences:
Suppose you start off with a finite sequence containing one term:
S0 = {3}
To get the next sequence you ...
3
votes
0
answers
83
views
Is this sequence periodic?
Suppose we have a sequence of numbers, $$t_n$$
Such that $$t_{2n} = t_n$$
and
$$t_{2n+1} = 1 - t_n$$
Also, $$t_0 = 1$$
Is this sequence periodic?
I have found that the sequence of numbers comprise ...
- 127
3
votes
0
answers
124
views
Solving recurrences using substitution method
I have given
$$
T(n)= \begin{cases} T(n/3)+T(2n/3)+n,\quad &n>1 \\
1, \quad &n=1
\end{cases}
$$
I tried it again and again but couldn't think beyond,
$$
T(n)=T(n/27)+3T(...
- 31
3
votes
1
answer
222
views
SICP: Why does this recursion-based sine approximation work?
Here is the question and solution to Structure and Interpretation of Computer Programs' exercise 1.15 (see here). My problem is, I don't know how the combination of these formulae actually work:
$$...
- 948