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 ...
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 ...
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_{...
Community wiki
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$...
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}(\...
Top 50 recent answers are included
Related Tags
recursion × 538algorithms × 166
recurrence-relation × 88
algorithm-analysis × 77
runtime-analysis × 56
time-complexity × 55
dynamic-programming × 53
computability × 51
asymptotics × 35
trees × 24
master-theorem × 22
induction × 19
divide-and-conquer × 18
complexity-theory × 17
graphs × 16
data-structures × 16
binary-trees × 15
turing-machines × 14
proof-techniques × 14
combinatorics × 13
primitive-recursion × 13
terminology × 12
discrete-mathematics × 12
functional-programming × 11
iteration × 11