Introductions to functional programming, and especially Lisp, traditionally have a lot of exercises involving recursion on lists. Students are expected to reimplement standard functions like
reverse, and sometimes dubious ones like
flatten. This makes a certain amount of sense: if you're trying to teach recursion and lists, why not cover both at once?
For one thing, it makes functional programming look bad. How many students have learned from such material that Lisp is about recursion (and strangely named
cdr operators), without any hint of why it's so highly regarded, or of what else it can do? How many have learned (or had their prejudice reinforced) that functional programming is a silly academic game with no relevance to actual programming?
It also teaches students bad habits. Experienced functional programmers follow the heuristic: if you're recursing on lists, you should probably be using some high-order function instead. Even if it's one of the awkward ones like
concatMap. (Awkward in that code using them is often harder to read than that using
filter, though not as hard as plain recursion.) But beginners are taught to do things the hard way.
Some recursion exercises also operate on multiple levels of list structure, such as
flatten or a multilevel
reverse. Which is odd, because arbitrarily nested lists are rare in practice (except in code, which has its own complexities). These exercises teach students to recurse on both car and cdr, when they should instead be learning that lists are recursive only in the cdr. (ML and Haskell are spared this problem, as their type systems cannot readily conceive of arbitrarily nested lists. This is an advantage of restrictive static typing I hadn't considered.)
One of the most important lessons to learn about recursion is how widely applicable it is: it's not just for lists, or for recursive data structures; it's for any problem that can be broken down into smaller problems. Teaching recursion only on lists obscures this, leading students to think it's a specialized tool for one data structure, rather than one of the most general tools for creating algorithms.
It would be more natural to teach structural recursion on trees — directory trees, for instance, or at any rate something that naturally has tree structure. (Not search trees, because students who aren't yet comfortable with recursion won't understand why anyone would want such a structure. And not expression trees, because code-as-data is a lot for beginners to swallow, and it teaches them that functional languages are only for writing compilers for functional languages.) Non-structural recursion could be taught with the same sort of not-obviously-recursive problems that are used to teach dynamic programming.
(Prompted by some Clojure exercises which exhibit some of these problems.)