Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,354
questions
2
votes
1
answer
159
views
Reasoning about the Collatz conjecture, multiple infinitely growing trees that never overlap? [closed]
I have been pondering the Collatz conjecture recently as a mental exercise, and have run into a problem that has to do with proving that an iteratively growing tree of odd positive integers will ...
- 55
-2
votes
1
answer
48
views
Generate set of numbers containing 3 consecutive 1, but without the elements of the previous set [closed]
So I have this specific problem that I couldn't figure out. I want to create a set $F_n$ containing all bitstrings that has 3 consecutive 1s, but not those that are already contained in all the ...
- 713
0
votes
1
answer
57
views
Division based recurrences instead of subtraction based: $F(x)=F(x/2)+F(x/3)$
The most famous (and simplest non-trivial) recurrence is the Fibonacci recurrence $F(n)=F(n-1)+F(n-2)$ with $F(0)=0, F(1)=1$. What if we consider instead division based recurrences, the simplest non-...
- 8,945
0
votes
0
answers
27
views
How to best approach a numerical computational solution towards matching $e^{-r}$ and $k_2\sin(k_1\,r)$ as well as their derivatives $\frac{d}{d\,r}$?
In my question, "Why does it seem like two parameters $k_1$ and $k_2$ are needed to match $e^{-r}$ and $k_2\sin(k_1\,r)$ as well as their derivatives $\frac{d}{d\,r}$?", it was identified ...
- 951
0
votes
1
answer
105
views
Why doesn't this diagonal argument work?
I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the ...
- 27
0
votes
1
answer
39
views
How to Prove Division of One Bezier Curve into Two using de Casteljau Algorithm
$\newcommand{\brstbasis}[2]{b^{#1}_{#2}}$
$\newcommand{\posintset}{\mathbb{Z}^{+}}$
$\newcommand{\intset}{\mathbb{Z}}$
$\newcommand{\realset}{\mathbb{R}}$
$\newcommand{\domain}[1]{\operatorname{dom}\...
- 1,840
0
votes
0
answers
23
views
Recursive approximations of inverse square law
I have a toy electrostatics simulation that consists of some number of 2D point particles that each have a real-valued "charge" $q_i$, which then exert forces on each other proportional to $...
- 640
0
votes
1
answer
121
views
Tried finding an efficient algorithm for a 4-digit number guessing game, knowing only the number of digits on correct positions..
I've been playing a game similar to Bulls and Cows, but it goes like this: one player has to pick a random $4$ digit number. Digits can repeat, any digit between $0$ to $9$ and, you only get the ...
- 3
0
votes
2
answers
21
views
Find limit of Decrementing Recursive Series
I want to find a formula to find the lower limit part of this recursive or geometric series
$$
x_{n} = \left( x_{n-1} + p \right) \times \left( 1 - \frac{t}{100} \right)
$$
I was just wondering what ...
- 13
0
votes
4
answers
107
views
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing where $x_1$ $> 0$.
I have been asked the above question and the working out given to me skipped some steps in between.
It ...
- 618
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
1
vote
1
answer
29
views
Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem
I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf.
The simplified ...
- 102
2
votes
1
answer
77
views
Let $x_0 = 3;\ x_{n+1}=3x_n\ $ if $\ \frac{x_n}{2}<1;\ x_{n+1}=\frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\ $ Is $\ \liminf_{n\to\infty} x_n=1?$
This is a natural follow-up question of this previous question of mine.
Let $x_0 = 3.$ Let $\ x_{n+1} = 3x_n\ $ if $\ \frac{x_n}{2}<1;\quad x_{n+1} = \frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\quad ...
- 20.7k
0
votes
0
answers
25
views
Further explain natural language explanation for statements deduced from master theorem for solving recurrences
This content is taken from from Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 2022, Chapter 4.
Given the following recurrence ...
- 81
3
votes
2
answers
190
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53