A small explanation why the difference in execution times is so gigantic.
When you calculate by iteration it is very clear to see that you need only 28 loops to calculate the 30th Fibonacci number. Numbers 0 and 1 are 0 and 1 respectively and for every next number you add the highest number to the lowest number. (The three MOV instructions make sure that I have the lowest number in register EBX.)
But for any recursive routine the number of calculations are NOT 28 (or 29 or 30). Let me show you.
F(0) = 0, that's simple.
F(1) = 1, that's also simple.
F(2) = F(1) + F(0). But that takes two calls.
F(3) = F(2) + F(1). That's also two calls but F(2) needs another two calls to be calculated. Four calls in total.
F(4) = F(3) + F(2). Again, two calls. But you need four more for F(3) and two more for F(2). Total: eight.
F(5) = F(4) + F(3). Two for this one, eight for F(4), and four for F(3). Total: fourteen.
This is also a sequence that looks like Fibonacci: the number of calls you need to calculate F(n) when n>3 is two plus the number of calls of F(n-1) and F(n-2). As we've seen F(2)=2 and F(3)=4. The sequence is the following: number for calls for F(n) starting at n=0.
0, 0, 2, 4, 8, 14, 24, 40, 66, 108, 176, 286, 464, etc. (See attached spreadsheet.)
For F(30) a total of 2692536 calls have to be made and that is why my iterative code is so much quicker.
Reply With Quote
Bookmarks