StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Because both algorithms work entirely different. Let me show you this with fib(5).</p> <p>if you call fib1(5), it internally calls fib1(4) und fib1(3), lets visualize that with a tree:</p> <pre> fib(5) / \ fib(4) fib(3)</pre> <p>now, fib(4) internally calls fib(3) and fib(2).</p> <p>So now we have this:</p> <pre> fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) </pre> <p>I think by now it is very obvious where this is going, you should be able to fill in the rest. </p> <p><strong>edit</strong>: Another thing you should notice here is, that it actually has to performe the same caclculation multiple times. In this picture, fib(2) und fib(3) are both called multiple times. And this gets worse if the starting number is bigger.<strong>/edit</strong></p> <p>Now, let's take a look at fib2(5). It you call it with 0, it returns 0. Otherwise, it calls fib2x(n, 0,1) So, we have a call to fib2x(5,0,1). fib2x(n, 0,1) now internally calls fib2x(n-1, p1, p0+p1) and so on. So, lets see:</p> <pre> fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5) </pre> <p>by then, it has reached the return condition and returns 5.</p> <p>So, your algorithms work entirely different. The first one works recursively and from the top to the bottom. The second one starts at 1 and works his way up. Actually, it is more iterative then recursive (it was probably written recursive to throw you off). It keeps the already calculated values instead of discarding them and therefore needs to invoke far less calculations.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload