1.5. Analysis


Perhaps the statistic that stands out in this data is the meager 39% of students able to successfully implement a recursive method. The specific task question asks students to implement a recursive method that counts the number of occurrences of some data value in a binary tree.

It might be argued that this problem is too difficult for CS46B students, but the success of such an argument would depend on the amount of coverage given to recursion, binary trees, and similar problems.

More importantly, the department needs to decide how much recursion students need to know. Is it a dying art, an anachronism from a more elegant age? Many practicing software engineers freely admit to not being comfortable with recursion. Many problems can be solved using recursion or (often more efficiently) iteration. Should the department accept that only 39% of CS46B students can implement a recursive method?

On the other hand, recursive solutions are often easier to find than equivalent iterative solutions (assuming the programmer is comfortable with recursion). In some cases-- e.g. implementing compilers and parsers-- iterative solutions are hard to find. If found they tend to be complex and messy.

In functional languages like LISP, Haskell, and XSLT iteration either doesn't exist (because of its dependence on the state of some loop control variable) or is grafted onto the language Frankenstein-style, the way goto statements are grafted onto structured languages. Instead, programmers are encouraged to eschew traditional control structures in favor of higher order recursive functions (such as map and filter). In effect, functional languages exploit the trade-off between complexity and abstraction.