Students should see recursion again in CS152, where they are required to learn a functional language. Perhaps the department should consider adding a task that addresses recursion to BSCS.OC11:
The ability to write programs of moderate sophistication in a functional programming language
Note: this outcome is scheduled to be assessed this fall.
Recursion tends to be second nature to students who learn Scheme as their first language. For this reason many top universities (MIT, Berkeley, Carnegie-Mellon) teach Scheme in their introductory programming course. Recursion is taught to children using the Logo programming language. (Years ago the SJSU CS department taught Logo and Scheme.)
Last semester CS40 students learned to solve difficult problems by building models using NetLogo, the agent-based successor of Logo. At the end of the semester students were able to build useful engaging models that used recursion.
The department might kill several birds with a single stone by strongly suggesting to incoming students with weak backgrounds that they take NetLogo-based CS40 class before taking CS46A.