New answers tagged recursion
-1
votes
Runtime complexity of permutation function
Consider this piece of code:
for i in range(len(nums)):
dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res)
Note that ...
- 791
1
vote
How are regular languages not structurally recursive?
Regular languages don't have recursive structures, so formally regular expressions cannot express recursive structures by definition.All regular languages can be recognized by a finite automaton. A ...
- 468
1
vote
Compute a commutative and associative operation on n-2 arguments efficiently
(Motivation: let $h = n/2$.
Given $f_{ih} = f(x_i\dots x_{h-1}) \text{ and } f_{hj} = f(x_h\dots x_j)$ (precomputed in about $n$ evaluations of $f$),
$f(x_{i+1}\dots x_{j-1})$ can be computed as $f(f_{...
2
votes
Accepted
Compute a commutative and associative operation on n-2 arguments efficiently
(1) You can compute $f(x_1,\dots,x_{i-1})$ for all $i$ with $n-2$ calls to $f$. (Simply iterate over $i:=1,\dots,n$.)
(2) Then, using (1), you can compute $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1})$ ...
D.W.♦
- 141k
0
votes
Compute a commutative and associative operation on n-2 arguments efficiently
Count how many times each $x_i$ occurs in the argument list.
Suppose $X_1$ is the set of $x_i$ that occur once, $X_2$ is the set of $x_i$ that occur twice, ..., $X_m$ is the set of $x_i$ that occur $m$...
- 115
0
votes
1
vote
Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive
Here is a recursive function for your problem:
\begin{align*}
& \mathrm{count6}(n) = \mathrm{cond}(\mathrm{eq}(n, 0), 0,\\
& \quad \mathrm{add}(\\
& \quad \quad \mathrm{cond}(\mathrm{eq}(\...
- 1,024
Top 50 recent answers are included