CIS 399-03: The Art of Recursion (Fall 2012)

TR 3-4:30
Levine 512

Class Piazza site

Class wiki


Instructor: Brent Yorgey

Course Description

Recursion is a second-class citizen in many mainstream programming languages. It has a reputation for being scary and confusing, and programmers are often explicitly instructed to avoid it. However, this is a real shame: recursion is a beautiful and foundational concept with links to many areas of computer science, mathematics, and art. At the very least, the competent programmer ought to have it as a viable tool in their toolbox. In this hands-on course we will demystify recursion and explore many of its facets. Potential topics include recursive data types and algorithms, structural recursion, induction, recurrence relations, tail-call optimization, guarded recursion, primitive recursion and recursive function theory, equivalence of recursion and iteration, domain theory and fixed points, termination analysis, and (last but not least!) recursion in art and music. Evaluation will be based on class participation, weekly problem sets and/or programming assignments, two midterm exams, and a final project.

Draft syllabus

Can you get from the + to the -? The boxes labeled A, B, and C each contain a complete copy of the entire maze. Be sure you end at the same level you started.