I would also add. Don't introduce a language by showing how to compute the Fibonacci sequence.
I never have and never will need to compute the Fibonacci sequence. Recursion is such an infrequent part of everyday programming that it doesn't really matter if a language makes it easier.
It is frequent in some applications, and when programming in languages that encourage you to recur instead of looping (see: functional proramming). Also, recursion is one of the most important concepts of computer science.
I didn't really use recursion in my programming until I switched from C++ to Common Lisp.
It's true that it's fairly infrequent, but it doesn't follow that it doesn't matter if a language makes it easier. When it's applicable, it simplifies things enormously.
I never have and never will need to compute the Fibonacci sequence. Recursion is such an infrequent part of everyday programming that it doesn't really matter if a language makes it easier.