>> And yet, I will use Fibonacci as introductory example tomorrow when I teach "Intro to computational complexity" this week. The great advantage of Fibonacci over just about anything else is that it is so short, so simple, that everybody can immediately understand it. There is no preparation needed. Just about anybody who can breath, can understand Fibonacci.
Despite this simplicity, Fibonacci is so rich: You can use it to illustrate: Recursion, exponential complexity, going from exponential to linear complexity by memoisation. Relationship between loops and recursion. Tail calls. Stack space used by compilers, the limitations of compilers that do not do proper tail call optimisation,generating functions, recurrences, solving recurrences.
I agree with all you said too ;-)
I would say "Intro to computational complexity" is a more advanced course and the students should already be familiar with recursion from experience prior to learning to analyze time complexity ;-)
IMHO Fibonacci is still a poor example because the most obvious (to me) implementation has always been a loop. Pointing out how a recursive version can be simplified to a loop seems silly, and so does making it more efficient with memoization. But as a first example, sure I suppose. Then you drop the bomb on them and show how it can be done in O(log(n)) by using fast matrix exponentiation.
Thanks for reminding me of the O(log(n)) algorithm. I had forgotten about it. Just added this algorithm to the lecture slides. I <3 the internet.
I start with the recursive algorithm because it follows directly from the definition F(n+2) = F(n) + F(n+1). I also think there's a big schism in programmers: between those that think recursively, and those that are of a more iterative bend. I'm in the former camp, probably owing to the fact that my first programming language was Scheme.
Despite this simplicity, Fibonacci is so rich: You can use it to illustrate: Recursion, exponential complexity, going from exponential to linear complexity by memoisation. Relationship between loops and recursion. Tail calls. Stack space used by compilers, the limitations of compilers that do not do proper tail call optimisation,generating functions, recurrences, solving recurrences.
I agree with all you said too ;-)
I would say "Intro to computational complexity" is a more advanced course and the students should already be familiar with recursion from experience prior to learning to analyze time complexity ;-)
IMHO Fibonacci is still a poor example because the most obvious (to me) implementation has always been a loop. Pointing out how a recursive version can be simplified to a loop seems silly, and so does making it more efficient with memoization. But as a first example, sure I suppose. Then you drop the bomb on them and show how it can be done in O(log(n)) by using fast matrix exponentiation.