# Questions tagged [recursive-algorithms]

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

1,070 questions
Filter by
Sorted by
Tagged with
15 views

39 views

### How to calculate the following variance in a recursive way

Suppose we need to divide people into two groups A and B, the first person will be assigned to either of the group with probability $0.5$, from the second person, the assignment will be done based on ...
8 views

### Recursive function / conditional asymptotics

Let $t(n):=t(\lfloor \frac{n}{2} \rfloor)+t(\lceil \frac{n}{2} \rceil)+c⋅n$ is $O(n ⋅log n)$ So obviously this is the merge-sort algorithm, it is demanded that we show t(n)∈O(n⋅logn) that by showing ...
106 views

### Any advantages of using Gödel universal functions in proving unsolvability?

Let $U$ be a universal function for the class of computable functions of one variable. This means that $U:N\times N\to N$ is a computable (partial) function and for every computable (partial) function ...
47 views

### Question about unclear definition of Ackermann-Péter function in Stanford Encyclopedia of Philosophy

I'm reading Recursive Functions at Stanford Encyclopedia of Philosophy (section 1.4). The following paragraph defines function β which is then used to define variant of Ackermann-Péter function: What ...
19 views

### Partitioning a log with minimum cost

I am struggling with a problem that requires me to find a general pattern and come up with a solving algorithm. The problem goes on like this: You are given a wood log of length L and a number n that ...
5 views

### Implementing L-Systems for conversion (instead of drawing): Extending the Hilbert space filling curve

I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
23 views

### Recursive Algorithm Question [closed]

I am having a difficult time figuring out where to start this problem. Any input on where to start would be greatly appreciated. Consider the recursive algorithm, which operates on a sequence of ...
24 views

48 views

139 views

### Recurrence relation with python. [closed]

How to find the terminating value of the continued fractions $$S=3-\cfrac2{3-\cfrac2{3-\cfrac2{\ddots}}}$$ by writing a recurrence relation in Python? (Start from any guess value other than 1.)
31 views

### Find a recursive formula for $a_n$, $n ≥ 2$, in terms of $a_{n−1}$ and $a_{n−2}$, where $a_0 = 0, a_1 = 1$

Find a recursive formula for $a_n$, $n\ge 2$, in terms of $a_{n-1}$ and $a_{n-2}$, where $a_0=0$, $a_1=1$, $a_2=-1$. The power series is $$\sum\frac{(-1)^{n-1}}{(n-1)!}$$ And can anyone help with ...
31 views

### Dynamic Programming Cheapest Train Ride Question

I am struggling with the below dynamic programming practice problem and I am hoping someone can help. The problem states: "You want to go from station 1 to station n by rail. The train fare from ...
30 views

### Expected size of a set with iterative probabilistic growth

We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches. We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
32 views

### How many ways are there to choose k from n such that the longest consecutive block chosen is j things long?

Denote the number of $\binom{n}{k}$ such that the longest consecutive block of things chosen is exactly $j$ things long as ${\binom{n}{k}}_{j}$, where $j\leq k \leq n$; the goal is to derive a general ...
74 views

### A question about the plastic number

The plastic number is well known to be the limiting ratio of the Padovan sequence (OEIS A000931), to wit, $$P_n=P_{n-2}+P_{n-3}\\ \lim_{n\to \infty} \frac{P_{n+1}}{P_n}=p$$ However, it is also the ...
22 views

### Algorithm for auto convolution

I have a question, since we have a divide and conquer algorithm for calculate normal convolution sequence in n^log(3) [n power log 3 base 2] , i thought maybe symmetric feature in auto-convolution can ...
47 views

### How to obtain a formula for $f(z)$ given this recurrence

I am trying to figure out how to derive a formula for $f(z)$ that is a function of $z$ and maybe $k \in \mathbb{N}$: $$f(z) = 1+z f \bigg(\frac{z}{1+z} \bigg)$$ As an attempt, I tried a change of ...