# Questions tagged [recursive-algorithms]

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

1,354 questions
Filter by
Sorted by
Tagged with
133 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 ...
• 57
47 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
56 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,885
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 ...
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 ...
39 views

• 640
101 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
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
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
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
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
71 views

• 496
52 views

### Telescoping recursive term ${D(h) = D(h-2)+1}$

In the context of Computer Science, I am trying to calculate the maximum depth difference between leaf nodes in any existing AVL-Trees of height $h$. I don't think any knowledge of AVL trees is needed,...
• 342
28 views

### Fast algorithms for computing $AGA^T$ with $G$ PSD symmetric.

Problem: In the context of decision making in some optimization problems, I found that it is meaningful to compute $AGA^T$ with $A\in\mathbb R^{m\times n}$ and $G\in\mathbb R^{n\times n}$ a PSD ...
• 6,076
92 views

### 3d fractal helix modeling

I'm trying to build a 3d visual to illustrate a concept. Imagine a circular helix. We could define a cylinder that contains that helix. But now imagine this cylinder takes the helicoïd shape too ! We ...
1 vote
128 views

### How do I convert my recursive algorithm to an explicit formula? [closed]

I have the recursive formula: \begin{align} x_1&=1-\frac{1}{e} \\ x_{n+1}&=1-(1-x_n)^{1/x_n} \end{align} Is there any way to write this as an explicit formula? I've tried writing the exact ...
61 views

### Divide and conquer algorithm problem applied to an n x n-matrix of n players competing in a chess tournament [closed]

A total of n players have competed in a chess tournament. In particular every pair of players i and j played one single game. All results of the tournament are encoded in a n × n-matrix A, where for ...
1 vote
### Big-O complexity of a recurrence function $8 \cdot T(\frac{n}{4})+O(n\cdot\sqrt{n})$
An algorithm solves a problem of size $n$ by recursively calling 8 subproblems, with each subproblem of 1/4 the size of the original input. It then combines their solutions to form the solution of the ...