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.
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.
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.
And that would be me ;-)
I started programming as a kid because I wanted to make games. It was fun. The problem was that I didn't get the more formal stuff until college, and it made me a much better programmer. But I could also see how boring the data structures class would be to someone with no experience because they really didn't have insight into how applicable some of the concepts could be.
I have always advocated for creating games (and other useful things) to teach programming. Most if not all the major concepts can be applied to games. Why anyone would use the fibonacci sequence to teach recursion is beyond me - it's a stupid solution to a stupid problem. Let's talk about board games and minimax search. Yeah, you have to build a lot of code before that comes into play but you'll learn a hell of a lot more and have way more fun doing it.
Doing simple games like 2D scorched earth really brings home basic vector math and physics. Any 80's arcade game with a thrust button allows you to apply that stuff.
Any kind of 3d graphics goes right along with linear algebra - a topic that is not required by all CS programs even though matrix operations run 24/7 on supercomputers.
Text processing. chat bots anyone?
I used to have an example that used trees but it escapes me right now. Chess doesn't really count because you don't store the tree. We can go back to 3d graphics of course - photon mapping, kd-trees, various BVH structures.
If you start with data structures and algorithms, peoples eyes will glaze over. If you start with simple things that are somewhat interesting you'll get people interested and then you can progress them slowly to more advanced topics by introducing problems they'll want to solve.