|
General Details
|
|
C++
|
|
Posted 4.3 Years Ago
|
|
689 Views
|
|
Received 2 Ratings
|
|
Contrasting Recursion, Iteration, and memoization for Fibonacci's Sequence
Description
Here is some code that I made to contrast the execution time of a couple differently styled methods. All of them all recursive procedures, but some of the functions produce a iterative process (namely, the tail-recursive ones).
Each function calculates a term of Fibonacci's sequence. Each functions is timed to the time it takes to output the first 1400 terms of this sequence.
fibonacci(int n);
This one combines the simplest solution, using tree recursion, but I include memoization, a dynamic programming technique, to see how much more efficient that will make it.
fib2(double n1, double n2, int terms);
This is the plain tree recursive version. The simplest to code and understand, but hugely inefficient.
fib3(double n1, double n2, int terms);
This is the plain tail-recursive version. It generates and iterative process.
fib4(double n1, double n2, int terms)
This version applies the memoization technique to the tail-recursive version
Here are the results:
Memoization + Recursion: 1.562 seconds
Memoization + Iteration: 1.5 seconds
Iteration: 1.453 seconds
Recursion: much too long to time.
I'm curious as too why memoization actually slows down the iterative approach. If anyone knows, please let me know :) So what do you think of my little experiment :)
Source Code
Comments
| Please login to post comments. |
|
|
Hi,
The reason why you are not seeing a difference in performance is definitely related
to the issue that you are always doing recursive computation. fib3 is a recursive
function.
Another issue you might be facing is the way you define your static hash. I would
define it as a global variable outside of any of the functions. For the values up to
1,400 for Fib you should really see a performance increase using dynamic programming.
|
|
|
lol. I'm glad you enjoyed it. I didn't get what you meant with iostream
though.
|
|
|
also, it can do my math homework :)
|
|
|
Yeah, i copied that into DEVC++, and after it is done, type <iostream> makes it
do alot more, complex calculations.
|
More "C++" Source Codes By This Author
Recently Posted "C++" Source Codes
Recently Rated "C++" Source Codes
|
