New answers tagged recursion
0
You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$.
$$f(n, i) = \begin{cases}
1 & \text{if } n =0\\
f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\
0 & \text{otherwise}\\
\end{cases}$$
Then $...
4
Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function
$$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$
should match the description of the function given and proves that it is recursive.
Edit:
To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \...
3
You are unsure how to answer the question.
When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come.
A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls.
Now ...
1
Without going into the details, you are looking for something that's known as a Gray code. Any cyclic Gray code that has the all zero bitstring at the opposite part of the cycle as the all one bitstring gives a minimal expected solution time assuming an uniform random input.
2
Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$.
Input: coin 0, coin 1, coin 2, ..., coin $n-1$
Procedure:
$\quad$ If all coins face the same side, return.
$\quad$ For $i$ from 1 to $2^{n-1}-1$ inclusive:
$\quad\quad$ If $i$ is divisible by $2^k$ but not $2^{k+1}$:
$\quad\quad\quad$ Flip coin $k$
$\quad\quad\quad$ If ...
Top 50 recent answers are included
