Articles of recursive algorithms

Counting permutations, with additional restrictions

There are 10 slots and some marbles: 5 red, 3 blue, 2 green, how many ways can you fit those marbles into those slots? Those marbles fit in 10!/(5! 3! 2!) ways Now we have 10 slots but the slots have a restriction: slots #1 thru #4 can fit red, blue, or green marbles. But […]

Prove algorithm correctness

I’m wondering if there exists any rule/scheme of proceeding with proving algorithm correctness? For example we have a function $F$ defined on the natural numbers and defined below: function F(n,k) begin if k=0 then return 1 else if (n mod 2 = 0) and (k mod 2 = 1) then return 0 else return F(n […]

Cooley-Tukey FFT with arbitrary radices

The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by multiplying the twiddle factor by $-1$. (See the fourth paragraph in that section). Now, let’s say we have a higher radix. […]

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen’s matrix multiplication algorithm – $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with the base case $T(1) = 1$ and $n = 2^j$, I have been able to reduce the formula to the following form: $$T(2^j) = 7^j + \frac{3}{2}\,4^{j} […]

Recurrence Relation for Strassen

I’m trying to solve the following recurrence relation (Strassen’s):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} $$ So I multiplied the $7$ by $2$ several times and the 18n^2^2 several times and ended up with this general equation:- $$ 7k T(n/2^k) + […]

To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself: def f(): f() It’s not very complicated, the first line defines the function, and the second line calls it. Therefore, once the function is initially called, it will be continued to be called forever, as there is no base case. I […]

Where do the first two numbers of Fibonacci Sequence come from?

This question already has an answer here: Why does the Fibonacci Series start with 0, 1? 5 answers

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 recursion according to $$ \small x_0 = 1 \qquad x_{k+1} = \left( {z^2 \over x_k}+x_k \right)/2 $$ where only $ \small z^2 […]

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N – 1$ starting from the top and columns numbered from $0$ to $N – 1$ starting from the left. A cell $(u, v)$ refers to the cell that is on the $u$-th row and the $v$-th column. Each cell contains […]

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting languages must be simpler, possibly even regular. I don’t see how to prove this yet, so can you help me: […]