New answers tagged recursion
0
If holes are ignored (only the outline is computed), this is an instance of computing a single face of arrangement of half-lines (rays).
With half-lines, the maximum number of vertices in a single face is $\Theta(n)$. Therefore, this problem can be solved in $\Theta(n \log n)$ expected time using the randomized divide-and-conquer approach. See [1] chap.6.2 ...
1
Let $T_i$ be the tower defined by disks: $i,\dotsc,n$.
Here is a simple recursive algorithm:
Initialize i := 1
while(i != n+1)
If i is even:
move the tower T(i+1) on any rod other than C using the standard Tower of Hanoi algorithm.
move disk i to rod C
else:
move the tower T(i+1) on any rod other than B using the ...
0
Based on Navjot's answer, I think the complexity should be $𝑂(𝑚𝑛\times 3^s)$, because except the first step, you can only chose from 3 directions. You cannot go back to the previous position.
7
Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), noting that:
$F(0) = 0$
$F(1) = 1$
$F(2) = 1$
$F(3) = 2$
You'll see there's no disagreement at all.
Perhaps it would be informative to see the tree "grow&...
0
Your definition of substitution is doing too much work for EApp.
(a b)[e/x] = a[e/x] b[e/x]
sub x e (EApp a b) = EApp (sub x e a) (sub x e b)
For substitution the only interesting cases should be variables and binders. EApp is neither, so apply sub to its fields and reconstruct the term, without any additional matching, let recursion handle that.
20
I would like to say both you and that Berkeley tutorial are correct.
As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the nodes are different.
Every node in all figures represents a call to compute the corresponding Fibonacci number.
The difference is that you prefer to use ...
0
For a Directed Graph - we keep track of the recursion stack. For an edge (u,v), if we currently are processing u, and we see that v is in the recursion stack, then we have a Cycle.
For Undirected Graph - we look construct a parent array while we are traversing with DFS. Similar situation, for an edge (u,v) while processing u, if we see that v is Visited &...
0
Tail-recursive calls are better than other recursive calls because you can optimize away the return. Let’s say you try to write
fibonacci n =
fibonacci (n-1) +
fibonacci (n-2)
Can either call be optimized? No, because it'll turn into something like
push n on the stack
push the argument n-1
call fibonacci and save the return value
retrieve n from the ...
1
tail recustion is better becaus a good compiler can optimise it into a goto, thus it doesn't consume any stack space fro the recusrion or waste time returning.
foo(a){
m=bar(a);
if(z) return foo(a-1);
return m;
}
becomes
foo(a){
refoo:
m=bar(a);
if(z){
a=a-1;
goto re_foo;
}
return m;
}
46
if that is the only reason, why the compiler would not be able to optimize the regular recursive call?
You are focusing on the wrong thing here: the reason the optimization works is because of the tail part, not because of the recursion part.
Tail-recursion elimination is a special case of tail-call elimination, not a special case of some form of recursion ...
13
The way a standard function/procedure (from now on I'll just say "function") call works is that the caller needs to store onto the stack whatever state it needs for computations that occur after the call, and then the call occurs. Calling a function may also require manipulating the stack; on many current CPUs, issuing a call involves pushing the ...
Top 50 recent answers are included