You are viewing a single comment's thread from:
RE: Easy Tutorial: Computer Programming for DUMMIES (recursion made simple!)
I think someone would need to know what Big Oh is before they understand what you said. I could post about that, but I'm not sure how many people will read past the first few sentences, haha! You want to give a brief summary of that for the comments?
You don't need to explain Big O in the context of recursion and computing Fibonacci numbers. I was referring to how the function call stack will compute the same Fibonacci value multiple times.
For example, if we define F(n) = F(n-1) + F(n-2) with the base case of F(0) = 1, F(1) = 1, then F(4) = F(3) + F(2).
But then, F(3) calls F(2) + F(1) and F(2) calls F(1) + F(0), and we can easily see that F(2) is placed on the stack twice, F(1) is placed on the stack 3 times, and F(0) is placed on the stack twice.
A more efficient algorithm would be to store all pre-computed values in an array of size n + 1. Then, as you iteratively add the correct Fibonacci value to the array, you will note that you only compute each Fibonacci number once instead of multiple times as in the recursive algorithm. Consider the following pseudocode :
Now, we easily note that the computation for each fibs[i] is done only once. Comparing with the recursive algorithm, and it's easy to see that the iterative algorithm outperforms the recursive one.
There you go -- no need for explaining Big O, ;).
That's basically a like hash table right? You have an array, then a hash function that will give you the right value every time.
Why would you need a hash table?
I only used a stl vector for the contatiner because I didn't want to deal with dynamically allocated arrays of a particular size and then using memory allocation / deallocation in the pseudocode. I could've said
int fibs[n+1];but ... there's something really dissatisfying about doing that when n is not known at run time ...
But if you mean that the hash function is the trivial
hash(i) = ifunction and that you are saying that
fibs[hash(i)] <- F(i)where F(i) is the i'th Fibonacci number, then, yes, I suppose you could do that.No, I said it is like a hash table... I didn't say that we need a hash table! What I meant is that the array is like a hash table that holds all of the Fibonacci numbers, and calling fibs[x] is like the hash function for it. The more I try to explain this, the less this resembles a hash table, so I'm going to stop right there, haha! It just reminded me of a hash table because you can look things up very quickly (just like you can look up each Fibonacci number very quickly because they are already calculated in an the array).
Referring to what you said about optimal algorithms, not Big Oh.