Okay, so yesterday we saw one
way to generate the "nth" fibonacci number using recursion. The
recursion that we used is also called "tree recursion",
the reason for this being that we made two recursive calls inside the
function. If you were to draw a diagram of the function calls, the diagram
would take on the shape of a tree, because every node would have two
branches, like this:
If you tried to use this function to find the 35th fibonacci
number, you probably realized that it can take quite a bit of time. The
reason for this is that we are computing the same value many times over.
Consider what happens when you call Fibo(4). The function is going to add
Fibo(3) + Fibo(2). Fibo(3) will, in turn, call Fibo(2) + Fibo(1). So
you can see that we are calling Fibo(2) twice, which is a waste. Its
not a big deal for only the 4th fibonacci number, but when you put in 50, the
extra work can definitely start to make a difference.
See if you can come up with a way to speed up the function,
and I'll post my ideas tomorrow, along with a performance comparison of a
few different functions. Thanks for reading!
Joe posted a comment about my entry on the new nofollow attribute. He has a good idea to fix the problem I had, it would allow blog owners to selectively promote links in comments, so valid links would get their due "Google juice." I think this is a good idea, but I dont think many blog owners would be diligent in promoting peoples links, especially people who get a lot of comments.
What I would like is some sort of keyword list that I could maintain and links that contain these keywords would have the rel="nofollow" attribute. Then meaningful links to real blogs would still their credit. I would also want to be able to retroactively apply the keyword filtering, so if I get a bunch of comment spam one day, and I dont happen to have any keywords for the new spam, I would want to add the keywords, and then have the blogging application check my comments against my updated keywords list.